프로그램 명: city-driving
제한시간: 1 초
[요약]
최근 샌프란시스코를 여행을 시작했다. 그런데 운전하는 것이 고역이라는 것을 알았다.
관심 있는 도시는 N 개의 지점이다.
당신은 당신의 운전 경험을 증진하기로 결정 했다. GPS 가 없고 너무 많은 길을 기억할 수 없기 때문에
당신은 방향을 적었다. 그리고 N 개의 길이 얼마나 걸릴지를 (양방향으로 같다)
이 길로만으로 원하는 곳으로 이동할 수 있다.
주말 여행을 계획하고 있다.
입력으로 주어진 Q 지점으로 이동하는데 최단 거리를 구하는 것이 문제이다.
You recently started frequenting San Francisco in your free time and realized that driving in the city is a
huge pain. There are only N locations in the city that interest you, though, and you have decided to try
to improve your driving experience. Since you lack a GPS and cannot remember too many different routes,
you wrote down the directions and how long it takes to get between N di?erent pairs of locations (the same
in both directions), ensuring that using only these paths you can get from any location to any other one.
Now you are planning your trip for the weekend and you need to figure out the fastest way to get between
Q pairs of locations in the city using only the routes you have written down.
입력
-
The first line contains a single integer N, 3 ≤ N ≤ 100,000, the number of locations of interest and the number of routes you wrote down.
- The next N lines each contain three integers u, v, and w (1 ≤ w ≤ 1,000), indicating that you have directions from location u to location v
and vice-versa (0-indexed) which take w time.
The following line contains a single integer Q, 1 ≤ Q ≤ 10,000, the number of pairs of locations you need to compute the travel time for.
- The next Q lines each contain two integers u and v, indicating that you should find the minimum time to get from location u to location v.
출력
Print out Q lines, one for each pair of locations u and v you are finding the fastest routes
for. Each line should simply contain the minimum time it takes to travel from location u to location v.
입출력 예
입력
7
0 1 2
0 2 3
1 3 2
2 3 8
2 4 3
3 5 1
1 6 7
3
4 5
0 6
1 2
출력
11
9
5
출처:standford/2011/
[질/답]
[제출 현황]
[푼 후(0)]