Dijkstra:
#include <iostream> #include <vector> #include <algorithm> #include <queue> #include <cstring> # define LL long long using namespace std; int N; int M; int len[500][500]; int ti[500][500]; int S,T; int dispre[500]; int mindis[500]; int needtime[500]; int fastest[500]; int needsection[500]; int fastpre[500]; struct comp{ bool operator()(vector<int> p1, vector<int> p2){ return p1[1]>p2[1]; } }; void shortestPath(){ priority_queue<vector<int>, vector<vector<int>>, comp> pq; // {site,dis} memset(mindis,127,sizeof(mindis)); mindis[S]=0; needtime[S]=0; pq.push({S,0}); vector<int> completed(N,0); while(!pq.empty()){ auto cur=pq.top(); pq.pop(); int u=cur[0]; if(u==T) break; if(completed[u]==1) continue; completed[u]=1; int d=cur[1]; int t=needtime[u]; for(int i=0;i<N;i++){ if(len[u][i]==-1 || completed[i]==1) continue; if(d+len[u][i]<mindis[i]){ mindis[i]=d+len[u][i]; dispre[i]=u; needtime[i]=t+ti[u][i]; pq.push({i,mindis[i]}); }else if(d+len[u][i]==mindis[i]){ if(t+ti[u][i]<needtime[i]){ dispre[i]=u; needtime[i]=t+ti[u][i]; } } } } } void fastestPath(){ priority_queue<vector<int>, vector<vector<int>>, comp> pq; // {site,time} memset(fastest,127,sizeof(fastest)); fastest[S]=0; needsection[S]=0; pq.push({S,0}); vector<int> completed(N,0); while(!pq.empty()){ auto cur=pq.top(); pq.pop(); int u=cur[0]; if(u==T) break; if(completed[u]==1) continue; completed[u]=1; int t=cur[1]; int s=needsection[u]; for(int i=0;i<N;i++){ if(len[u][i]==-1 || completed[i]==1) continue; if(t+ti[u][i]<fastest[i]){ fastest[i]=t+ti[u][i]; fastpre[i]=u; needsection[i]=s+1; pq.push({i,fastest[i]}); }else if(t+ti[u][i]==fastest[i]){ if(s+1<needsection[i]){ fastpre[i]=u; needsection[i]=1+s; } } } } } int main(){ scanf("%d %d", &N, &M); memset(len,-1,sizeof(len)); memset(ti,-1,sizeof(ti)); memset(dispre,-1,sizeof(dispre)); for(int i=0;i<M;i++){ int a,b,c,d,e; scanf("%d%d%d%d%d", &a, &b, &c ,&d, &e); len[a][b]=d; ti[a][b]=e; if(c==0){ len[b][a]=d; ti[b][a]=e; } } scanf("%d%d", &S, &T); shortestPath(); vector<int> path; int v=T; path.push_back(v); while(true){ v=dispre[v]; path.push_back(v); if(v==S) break; } fastestPath(); vector<int> fapath; v=T; fapath.push_back(v); while(true){ v=fastpre[v]; fapath.push_back(v); if(v==S) break; } int issame=1; if(path.size()!=fapath.size()){ issame=0; }else{ for(int i=0;i<path.size();i++){ if(path[i]!=fapath[i]){ issame=0; break; } } } if(issame==1){ //Distance = 3; Time = 4: 3 -> 2 -> 5 printf("Distance = %d; Time = %d: ", mindis[T], fastest[T]); for(int i=path.size()-1;i>=0;--i){ if(i!=path.size()-1){ printf(" -> "); } printf("%d", path[i]); } return 0; } //Distance = 6: 3 -> 4 -> 8 -> 5 printf("Distance = %d: ", mindis[T]); for(int i=path.size()-1;i>=0;--i){ if(i!=path.size()-1){ printf(" -> "); } printf("%d", path[i]); } printf(" "); printf("Time = %d: ", fastest[T]); for(int i=fapath.size()-1;i>=0;--i){ if(i!=fapath.size()-1){ printf(" -> "); } printf("%d", fapath[i]); } return 0; }
另一种写法：
struct comp{ bool operator()(vector<int> p1, vector<int> p2){ if(p1[1]==p2[1]) return p1[2]>p2[2]; return p1[1]>p2[1]; } }; void shortestPath(){ priority_queue<vector<int>, vector<vector<int>>, comp> pq; // {site,dis,time} memset(mindis,127,sizeof(mindis)); mindis[S]=0; needtime[S]=0; pq.push({S,0,0}); vector<int> completed(N,0); while(!pq.empty()){ auto cur=pq.top(); pq.pop(); int u=cur[0]; if(u==T) break; if(completed[u]==1) continue; completed[u]=1; int d=cur[1]; int t=cur[2]; for(int i=0;i<N;i++){ if(len[u][i]==-1 || completed[i]==1) continue; if(d+len[u][i]<mindis[i]){ mindis[i]=d+len[u][i]; dispre[i]=u; needtime[i]=t+ti[u][i]; pq.push({i,mindis[i],needtime[i]}); }else if(d+len[u][i]==mindis[i]){ if(t+ti[u][i]<needtime[i]){ dispre[i]=u; needtime[i]=t+ti[u][i]; pq.push({i,mindis[i],needtime[i]}); } } } } }
SPFA:
#include <iostream> #include <vector> #include <algorithm> #include <queue> #include <cstring> # define LL long long using namespace std; int N; int M; int len[500][500]; int ti[500][500]; int S,T; int dispre[500]; int mindis[500]; int needtime[500]; int fastest[500]; int needsection[500]; int fastpre[500]; struct comp{ bool operator()(vector<int> p1, vector<int> p2){ return p1[1]>p2[1]; } }; void shortestPath(){ queue<int> q; memset(mindis,127,sizeof(mindis)); mindis[S]=0; needtime[S]=0; q.push(S); vector<int> inque(N,0); inque[S]=1; while(!q.empty()){ int u=q.front(); q.pop(); inque[u]=0; for(int i=0;i<N;i++){ if(len[u][i]==-1) continue; if(mindis[u]+len[u][i]<mindis[i]){ mindis[i]=mindis[u]+len[u][i]; dispre[i]=u; needtime[i]=needtime[u]+ti[u][i]; if(inque[i]==0){ q.push(i); inque[i]=1; } }else if(mindis[u]+len[u][i]==mindis[i]){ if(needtime[u]+ti[u][i]<needtime[i]){ dispre[i]=u; needtime[i]=needtime[u]+ti[u][i]; if(inque[i]==0){ q.push(i); inque[i]=1; } } } } } } void fastestPath(){ queue<int> q; memset(fastest,127,sizeof(fastest)); fastest[S]=0; needsection[S]=0; q.push(S); vector<int> inque(N,0); inque[S]=1; while(!q.empty()){ int u=q.front(); q.pop(); inque[u]=0; for(int i=0;i<N;i++){ if(len[u][i]==-1) continue; if(fastest[u]+ti[u][i]<fastest[i]){ fastest[i]=fastest[u]+ti[u][i]; fastpre[i]=u; needsection[i]=needsection[u]+1; if(inque[i]==0){ q.push(i); inque[i]=1; } }else if(fastest[u]+ti[u][i]==fastest[i]){ if(needsection[u]+1<needsection[i]){ fastpre[i]=u; needsection[i]=needsection[u]+1; if(inque[i]==0){ q.push(i); inque[i]=1; } } } } } } int main(){ scanf("%d %d", &N, &M); memset(len,-1,sizeof(len)); memset(ti,-1,sizeof(ti)); memset(dispre,-1,sizeof(dispre)); for(int i=0;i<M;i++){ int a,b,c,d,e; scanf("%d%d%d%d%d", &a, &b, &c ,&d, &e); len[a][b]=d; ti[a][b]=e; if(c==0){ len[b][a]=d; ti[b][a]=e; } } scanf("%d%d", &S, &T); shortestPath(); vector<int> path; int v=T; path.push_back(v); while(true){ v=dispre[v]; path.push_back(v); if(v==S) break; } fastestPath(); vector<int> fapath; v=T; fapath.push_back(v); while(true){ v=fastpre[v]; fapath.push_back(v); if(v==S) break; } int issame=1; if(path.size()!=fapath.size()){ issame=0; }else{ for(int i=0;i<path.size();i++){ if(path[i]!=fapath[i]){ issame=0; break; } } } if(issame==1){ //Distance = 3; Time = 4: 3 -> 2 -> 5 printf("Distance = %d; Time = %d: ", mindis[T], fastest[T]); for(int i=path.size()-1;i>=0;--i){ if(i!=path.size()-1){ printf(" -> "); } printf("%d", path[i]); } return 0; } //Distance = 6: 3 -> 4 -> 8 -> 5 printf("Distance = %d: ", mindis[T]); for(int i=path.size()-1;i>=0;--i){ if(i!=path.size()-1){ printf(" -> "); } printf("%d", path[i]); } printf(" "); printf("Time = %d: ", fastest[T]); for(int i=fapath.size()-1;i>=0;--i){ if(i!=fapath.size()-1){ printf(" -> "); } printf("%d", fapath[i]); } return 0; }