https://pintia.cn/problem-sets/1218775317992300544/problems/1218775886605705228
#include<iostream> #include<vector> #include<algorithm> #include<string> #include<map> #include<set> #include<cstring> using namespace std; #define STDIN freopen("in.in", "r", stdin);freopen("out.out", "w", stdout); int g[1000][1000]; int time1[1000][1000]; int len[1000][1000]; int distime[1000]; int dislen[1000]; bool bst[1000]; int n,m; int pre1[1000]; int pre2[1000]; int st, ed; vector<int> vec1; vector<int> vec2; int step1[1000]; int step2[1000]; int dijkstra1(int st, int ed) { dislen[st] = 0; // bst[st] =true; step2[st] = 1; memset(bst,0,sizeof bst); for (int i = 0; i < n-1; i++) { int t = -1; for (int j= 1; j <= n; j++) { if (!bst[j] && (t == -1 || dislen[j] < dislen[t] )) t = j; } for (int j = 0; j< n; j++) { if (dislen[t] + len[t][j] < dislen[j]){ dislen[j] = min(dislen[j], dislen[t] + len[t][j]); pre2[j] = t; step2[j] = step2[t]+1; } if (dislen[t] + len[t][j] == dislen[j]){ if (step2[j] > step2[t] + 1) { pre2[j] = t; step2[j] = step2[t] + 1; } } } bst[t] = true; } if (dislen[ed] == 0x3f3f3f3f) return -1; return dislen[ed]; } int dijkstra2(int st, int ed) { memset(dislen, 0x3f, sizeof dislen); distime[st] = 0; dislen[st] = 0; memset(bst,0,sizeof bst); for (int i = 0; i < n-1; i++) { int t = -1; for (int j= 1; j <= n; j++) { if (!bst[j] && (t == -1 || distime[j] < distime[t] )) t = j; } for (int j = 0; j< n; j++) { if (distime[t] + time1[t][j] < distime[j]){ distime[j] = min(distime[j], distime[t] + time1[t][j]); pre1[j] = t; dislen[j] = dislen[t] + len[t][j]; // step1[j] = step1[t] + 1; } if (distime[t] + time1[t][j] == distime[j]) { if (dislen[j] > dislen[t] + len[t][j]) { pre1[j] = t; dislen[j] = dislen[t] + len[t][j]; } } } bst[t] = true; } if (distime[ed] == 0x3f3f3f3f) return -1; return distime[ed]; } void print1(int x) { if (x != -1) { print1(pre1[x]); // cout << x; vec1.push_back(x); } // if (x == ed) cout << endl; } void print2(int x) { if (x != -1) { print2(pre2[x]); // cout << x; vec2.push_back(x); } // if (x == ed) cout << endl; } bool f(vector<int> & a, vector<int> &b) { int len = a.size(); for (int i = 0; i < len; i++) { if (a[i] != b[i]) return false; } return true; } int main() { // int n, m; // STDIN cin >> n >> m; memset(len, 0x3f,sizeof len); memset(time1, 0x3f, sizeof time1); memset(pre1, -1, sizeof pre1); memset(pre2, -1, sizeof pre2); memset(step1, 0x3f, sizeof step1); memset(step2, 0x3f, sizeof step2); memset(dislen, 0x3f, sizeof dislen);memset(distime, 0x3f, sizeof distime); for (int i = 1; i <= m; i++) { int a, b, c, d, e; cin >> a >> b >> c >> d >> e; len[a][b] = min(d, len[a][b]); time1[a][b] = min(e, time1[a][b]); if (c == 0){ len[b][a] = min(d, len[b][a]); time1[b][a] = min(e, time1[b][a]); } } cin >> st >> ed; int ans2 = dijkstra1(st, ed); int ans1 = dijkstra2(st, ed); print1(ed); print2(ed); if (f(vec1,vec2)) { printf("Time = %d; Distance = %d: ", ans1, ans2); int len = vec1.size(); for (int i = 0; i < len; i++) { cout<< vec1[i]; if (i == len-1) cout << endl; else cout << " => "; } } else{ printf("Time = %d: ",ans1); int len1 = vec1.size(); for (int i = 0; i < len1; i++) { cout<< vec1[i]; if (i == len1-1) cout << endl; else cout << " => "; } printf("Distance = %d: ",ans2); int len2 = vec2.size(); for (int i = 0; i < len2; i++) { cout<< vec2[i]; if (i == len2-1) cout << endl; else cout << " => "; } } }