http://codeforces.com/gym/101061/problem/C
Ramzi -Aufa‘s best friend- lives in the city of Rainland, Rainland is a very ordinary city except for one thing. It has a very Bad Weather!
The city is described as a set of intersections and a set of connections. Each pair of intersections is either connected with a cars-road, or with a pedestrian-road. Some pairs has a cars-road and a pedestrian-road connecting them and some pairs doesn‘t has any roads between them at all. You can assume that no pair has more than one pedestrian-road or more than one cars-road.
Ramzi can get a taxi to go from intersection A to intersection B if A and B has a cars-road connecting them, but he has to walk if it‘s a pedestrian road. Mostly he will be walking in the rain!
Ramzi is in intersection x and he want to meet Aufa in intersection y. Your job is to help him find the Optimal path form x to y.
The Optimal path is described as the path with the minimum walking time. If there is more than one path with the same minimum walking time, the Optimal path is the one with the minimum total time. The walking time for any path is the sum of the pedestrian-roads‘ time that occur in the path.
The total time for any path is the sum of its roads‘s time "pedestrian-roads and cars-roads" .
You can assume that Ramzi doesn‘t get wet when he is waiting for the taxi in some intersection, so we aren‘t interested in the waiting time for the taxi. Also he cant‘t walk throw any cars-road. So if he want to use a cars-road, he must take a taxi.
The first line of the input will contain T the number of test cases.
Each test case starts with two integers on a single line (0 < N ≤ 100), the number of the intersections, (0 < M ≤ N * (N - 1)), the number of the connections.
Then M lines follow, each describes a connection and contains four integers (0 < a ≤ N) , (0 < b ≤ N) , (0 ≤ c ≤ 10000) , (
). Which means that there is a connection between intersection a and intersection b that takes c minute of time. However if k is equal to 1 then it‘s a pedestrian-road, otherwise it‘s a cars-road. All connections are bidirectional. Meaning that you can use it to go both from a to b and from b to a. It‘s guaranteed that (a ≠ b).
Follows a line containing two integers (0 < x ≤ N), (0 < y ≤ N). which means that we are interested in the optimal path between intersection x and intersection y. It‘s guaranteed that (x ≠ y).
For each test case, if there is a path between x and y, you should print two integers on a separated line.
The first one should be the walking time in the optimal path. The second one should be the total time of the optimal path. If there isn‘t any path between x and y then you should print -1 on a separated line. See the sample output for more details.
3
3 3
1 2 5 1
1 3 5 2
3 2 4 1
1 2
2 2
1 2 5 2
1 2 3 1
1 2
3 1
1 2 5 1
1 3
4 9
0 5
-1
Large I/O files. Please consider using fast input/output methods.
题意：步行和车道两种道路。车道具有优先级。
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #include <algorithm> #include <iostream> #include<cstdio> #include<string> #include<cstring> #include <stdio.h> #include <queue> #include <string.h> #include <vector> #include <map> #define ME(x , y) memset(x , y , sizeof(x)) #define SF(n) scanf("%d" , &n) #define rep(i , n) for(int i = 0 ; i < n ; i ++) #define INF 0x3f3f3f3f #define mod 1024 using namespace std; typedef long long ll ; int ma1[1009][1009]; int ma2[1009][1009]; int dis1[1009]; int dis2[1009]; int vis1[1009]; int vis2[1009]; int n , m ; void Dijia(int r) { for(int i = 1 ; i <= n ; i++) { dis1[i] = ma1[r][i]; dis2[i] = ma2[r][i]; } vis1[r] = vis2[r] = 1 ; for(int i = 1 ; i < n ; i++) { int min1 = INF ; int min2 = INF ; int pos ; for(int j = 1 ; j <= n ; j++) { if(!vis1[j] && dis1[j] < min1) { min1 = dis1[j] ; min2 = dis2[j] ; pos = j ; } else if(!vis1[j] && dis1[j] == min1) { if(dis2[j] < min2) { min2 = dis2[j]; pos = j ; } } } if(min1 == INF || min2 == INF) break ; vis1[pos] = 1 ; vis2[pos] = 1 ; for(int j = 1 ; j <= n ; j++) { if(!vis1[j] && dis1[j] > dis1[pos] + ma1[pos][j]) { dis1[j] = dis1[pos] + ma1[pos][j]; dis2[j] = dis2[pos] + ma2[pos][j]; } else if(!vis1[j] && !vis2[j] && dis1[j] == dis1[pos] + ma1[pos][j]) { dis2[j] = min(dis2[j] , dis2[pos] + ma2[pos][j]); } } } } int main() { int t ; scanf("%d" , &t); while(t--) { scanf("%d%d" , &n , &m); memset(ma1 , INF , sizeof(ma1)); memset(ma2 , INF , sizeof(ma2)); memset(vis1 , 0 , sizeof(vis1)); memset(vis2 , 0 , sizeof(vis2)); for(int i = 1 ; i <= m ; i++) { int u , v , w , k; scanf("%d%d%d%d" , &u , &v , &w , &k); if(k == 1) { ma1[u][v] = ma1[v][u] = min(w , ma1[u][v]); } else if(k == 2) { ma2[u][v] = ma2[v][u] = min(w , ma2[u][v]); ma1[u][v] = ma1[v][u] = 0 ; } } for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= n ; j++) { if(ma1[i][j] != INF && ma2[i][j] == INF) { ma2[i][j] = 0; } } } int u , v ; scanf("%d%d" , &u , &v); Dijia(u); if(dis1[v] != INF) printf("%d %d\n" , dis1[v] , dis2[v] + dis1[v]); else printf("-1\n"); } return 0 ; }
原文：https://www.cnblogs.com/nonames/p/11379630.html