116 lines
3.8 KiB
TeX
116 lines
3.8 KiB
TeX
\documentclass{maratona}
|
|
|
|
\begin{document}
|
|
\begin{ProblemaAutor}{}{Quase Menor Caminho}{1}{1536}{SPOJ Brasil}
|
|
|
|
Encontrar o menor caminho entre dois pontos em um mapa é um problema clássico.
|
|
Mas, em alguns sistemas de navegação, todas as rotas que fazem parte de algum
|
|
menor caminho podem ficar congestionadas. Nesse caso, queremos encontrar uma rota
|
|
alternativa.
|
|
|
|
O mapa é representado por um grafo direcionado e ponderado. Os vértices são
|
|
pontos do mapa, e cada aresta direcionada representa uma rota de um ponto para
|
|
outro com um certo comprimento.
|
|
|
|
O quase menor caminho entre a origem $S$ e o destino $D$ é o menor caminho de
|
|
$S$ até $D$ que não usa nenhuma aresta pertencente a qualquer menor caminho de
|
|
$S$ até $D$ no grafo original.
|
|
|
|
Sua tarefa é determinar o comprimento do quase menor caminho. Caso não exista
|
|
nenhum caminho que satisfaça essa condição, a resposta deve ser $-1$.
|
|
|
|
Por exemplo, suponha que a figura abaixo representa o mapa dado, com círculos
|
|
representando localizações e linhas representando rotas diretas, de mão única
|
|
com as distâncias indicadas. O ponto de partida está marcado como $S$ e o de
|
|
destino está marcado como $D$. As linhas em negrito pertencem a um caminho
|
|
mínimo (nesse caso existem dois caminhos mínimos, cada um com extensão \(4\)).
|
|
Logo, o quase menor caminho seria o indicado com linhas pontilhadas (extensão
|
|
\(5\)), já que nenhuma rota entre dois pontos consecutivos pertence a nenhum
|
|
caminho mínimo. Note que poderia existir mais de uma resposta possível, por
|
|
exemplo, se a rota com extensão \(3\) tivesse extensão \(1\). Bem como poderia
|
|
inexistir uma resposta certa.
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\includegraphics[width=0.3\textwidth]{image.png}
|
|
\end{figure}
|
|
|
|
\Entrada
|
|
|
|
A entrada contem varios casos de teste.
|
|
|
|
A primeira linha de cada caso contem dois inteiros $N$ e $M$
|
|
($2 \leq N \leq 500$, $1 \leq M \leq 10^4$), representando o numero de
|
|
vertices e o numero de arestas direcionadas do grafo. Os vertices sao numerados
|
|
de $0$ a $N-1$.
|
|
|
|
A segunda linha contem dois inteiros $S$ e $D$
|
|
($0 \leq S, D < N$, $S \neq D$), representando a origem e o destino.
|
|
|
|
Cada uma das proximas $M$ linhas contem tres inteiros $U$, $V$ e $P$
|
|
($U \neq V$, $0 \leq U, V < N$, $1 \leq P \leq 1000$), indicando uma aresta
|
|
direcionada de $U$ para $V$ com peso $P$.
|
|
|
|
Existe no maximo uma aresta direcionada de um vertice $U$ para um vertice $V$.
|
|
A existencia de uma aresta de $U$ para $V$ nao implica a existencia de uma aresta
|
|
de $V$ para $U$.
|
|
|
|
O fim da entrada e indicado por uma linha contendo \texttt{0 0}.
|
|
|
|
\Saida
|
|
|
|
Para cada caso de teste, imprima uma linha contendo um unico inteiro.
|
|
|
|
Se existir um quase menor caminho, imprima seu comprimento. Caso contrario,
|
|
imprima $-1$.
|
|
|
|
\ExemploEntrada
|
|
\begin{Exemplo}
|
|
\texttt{7~9} & \texttt{5}\\
|
|
\texttt{0~6} & \texttt{-1}\\
|
|
\texttt{0~1~1} & \texttt{6}\\
|
|
\texttt{0~2~1} & \\
|
|
\texttt{0~3~2} & \\
|
|
\texttt{0~4~3} & \\
|
|
\texttt{1~5~2} & \\
|
|
\texttt{2~6~4} & \\
|
|
\texttt{3~6~2} & \\
|
|
\texttt{4~6~4} & \\
|
|
\texttt{5~6~1} & \\
|
|
\texttt{4~6} & \\
|
|
\texttt{0~2} & \\
|
|
\texttt{0~1~1} & \\
|
|
\texttt{1~2~1} & \\
|
|
\texttt{1~3~1} & \\
|
|
\texttt{3~2~1} & \\
|
|
\texttt{2~0~3} & \\
|
|
\texttt{3~0~2} & \\
|
|
\texttt{6~8} & \\
|
|
\texttt{0~1} & \\
|
|
\texttt{0~1~1} & \\
|
|
\texttt{0~2~2} & \\
|
|
\texttt{0~3~3} & \\
|
|
\texttt{2~5~3} & \\
|
|
\texttt{3~4~2} & \\
|
|
\texttt{4~1~1} & \\
|
|
\texttt{5~1~1} & \\
|
|
\texttt{3~0~1} & \\
|
|
\texttt{0~0} & \\
|
|
\end{Exemplo}
|
|
|
|
|
|
|
|
\Notas
|
|
|
|
No primeiro caso da amostra, existem menores caminhos de custo $4$. Todas as
|
|
arestas que aparecem em algum desses caminhos sao descartadas. Depois disso, o
|
|
menor caminho restante tem custo $5$.
|
|
|
|
No segundo caso, todo caminho da origem ate o destino usa alguma aresta que
|
|
pertence a um menor caminho original, entao a resposta e $-1$.
|
|
|
|
Problema adaptado do SPOJ Brasil:
|
|
\href{https://br.spoj.com/problems/QUASEMEN/}{QUASEMEN - Quase Menor Caminho}.
|
|
\end{ProblemaAutor}
|
|
\end{document}
|