题目分析：
本题的题意比较清晰，就是有一个起点和一个终点，给出m条路径，可能是单向的可能是双向的，同时一条路有两个权重，分别是通过这条路需要的时间和这条路的路径长度，题目需要求出两条路径，一条是在最快的基础上的最短路径，一条是在最短的路径的基础上的通过节点的数量最少的路径（题目保证这两条途径存在，且在各自的情况下唯一，但是这两条路径有可能完全相同，需要合并输出）
解法分析：
通过对题目的分析，我们知道最优的子情况就是全局的最优解，所以我们用两次dijkstra算法，一次求最短路径的情况下通过最少节点的路径记录在pre1中，一次求最快路径的基础上的最短路径，记录在pre2中，最后递归输出路径即可
代码：
1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<cmath> 5 #include<string.h> 6 using namespace std; 7 8 const int N = 505; 9 const int M = 0x3f3f3f3f; 10 int pre1[N]; 11 int pre2[N]; 12 int dist1[N]; 13 int dist2[N]; 14 int mat1[N][N]; //存储距离 15 int mat2[N][N]; //存储时间 16 int vis1[N]; 17 int vis2[N]; 18 int num[N]; 19 int n, m; 20 int min_dist, min_time; 21 int sta, en; 22 23 int minn1(){ 24 int k = -1; 25 int Min = M; 26 for(int i = 0; i < n; i++){ 27 if(vis1[i] == 0 && dist1[i] < Min){ 28 Min = dist1[i]; 29 k = i; 30 } 31 } 32 return k; 33 } 34 35 void dijkstra1(){ //计算最短距离 若有相同则选择途经的点最少的 36 memset(num, 0, sizeof(num)); 37 memset(vis1, 0, sizeof(vis1)); 38 for(int i = 0; i < n; i++) pre1[i] = sta; 39 for(int i = 0; i < n; i++) dist1[i] = mat1[sta][i]; 40 dist1[sta] = 0; 41 pre1[sta] = -1; 42 num[sta] = 1; 43 for(int i = 1; i <= n; i++){ 44 int k = minn1(); 45 if(k == -1) break; 46 vis1[k] = 1; 47 for(int j = 0; j < n; j++){ 48 if(vis1[j] == 0 && dist1[k] + mat1[k][j] < dist1[j]){ 49 dist1[j] = dist1[k] + mat1[k][j]; 50 pre1[j] = k; 51 num[j] = num[k] + 1; 52 }else if(vis1[j] == 0 && dist1[k] + mat1[k][j] == dist1[j]){ 53 if(num[j] > num[k] + 1){ 54 num[j] = num[k] + 1; 55 pre1[j] = k; 56 } 57 } 58 } 59 } 60 min_dist = dist1[en]; 61 } 62 63 int minn2(){ 64 int k = -1; 65 int Min = M; 66 for(int i = 0; i < n; i++){ 67 if(vis2[i] == 0 && dist2[i] < Min){ 68 Min = dist2[i]; 69 k = i; 70 } 71 } 72 return k; 73 } 74 75 void dijkstra2(){ //计算最少时间 若有最少时间相同 则选择最短距离 76 memset(vis2, 0, sizeof(vis2)); 77 for(int i = 0; i < n; i++) pre2[i] = sta; //因为sta会最先被选中 78 for(int i = 0; i < n; i++) dist2[i] = mat2[sta][i]; 79 dist2[sta] = 0; 80 pre2[sta] = -1; 81 for(int i = 1; i < n; i++){ 82 int k = minn2(); 83 if(k == -1) break; 84 vis2[k] = 1; 85 for(int j = 0; j < n; j++){ 86 if(vis2[j] == 0 && dist2[k] + mat2[k][j] < dist2[j]){ 87 dist2[j] = dist2[k] + mat2[k][j]; 88 pre2[j] = k; 89 }else if(vis2[j] == 0 && dist2[k] + mat2[k][j] == dist2[j]){ 90 if(mat1[pre2[j]][j] > mat1[k][j]){ 91 pre2[j] = k; 92 } 93 } 94 } 95 } 96 min_time = dist2[en]; 97 } 98 99 void way(int *pre, int x){ 100 if(pre[x] == -1){ 101 printf("%d", x); 102 return; 103 }else{ 104 way(pre, pre[x]); 105 printf(" => %d", x); 106 } 107 } 108 109 int main(){ 110 scanf("%d%d", &n, &m); 111 memset(mat1, M, sizeof(mat1)); 112 memset(mat2, M, sizeof(mat2)); 113 for(int i = 1; i <= m; i++){ 114 int a, b, c; 115 scanf("%d%d%d", &a, &b, &c); 116 if(c == 1){ 117 scanf("%d%d", &mat1[a][b], &mat2[a][b]); 118 }else{ 119 scanf("%d%d", &mat1[a][b], &mat2[a][b]); 120 mat1[b][a] = mat1[a][b]; mat2[b][a] = mat2[a][b]; 121 } 122 } 123 scanf("%d%d", &sta, &en); 124 min_dist = M; min_time = M; 125 dijkstra1(); 126 dijkstra2(); 127 //如果路径统一则合并输出 128 int flag = 1; 129 int temp = en; 130 while(true){ 131 if(temp == -1) break; //一定是在相等的基础上的-1 132 if(pre1[temp] == pre2[temp]) temp = pre1[temp]; 133 else{ 134 flag = 0; 135 break; 136 } 137 } 138 if(flag == 1){ 139 printf("Time = %d; Distance = %d: ", min_time, min_dist); 140 way(pre1, en); 141 printf(" "); 142 }else{ 143 printf("Time = %d: ", min_time); 144 way(pre2, en); 145 printf(" "); 146 printf("Distance = %d: ", min_dist); 147 way(pre1, en); 148 printf(" "); 149 } 150 return 0; 151 }