解题关键：最短路的变形。
1、按顶点存储，$O(n^2)$
#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<iostream> #include<cmath> #include<vector> #define inf 0x3f3f3f3f #define max_v 502 using namespace std; typedef long long ll; int pre[max_v],pathnum[max_v],toval[max_v],val[max_v]; int cost[max_v][max_v],d[max_v],used[max_v],V; void dijkstra(int s){ //边权和点权都是通过顶点体现 fill(d,d+V,inf); fill(used,used+V,0); fill(pre,pre+V,-1); d[s]=0; pathnum[s]=1; toval[s]=val[s]; while(true){ int v=-1; for(int u=0;u<V;u++){ if(!used[u]&&(v==-1||d[u]<d[v])) v=u; } if(v==-1) break; used[v]=true; for(int u=0;u<V;u++){ if(used[u]==false&&cost[u][v]!=inf){//???? if(d[u]>d[v]+cost[v][u]){ d[u]=d[v]+cost[v][u]; pre[u]=v; pathnum[u]=pathnum[v]; toval[u]=toval[v]+val[u]; }else if(d[u]==d[v]+cost[v][u]){ pathnum[u]+=pathnum[v]; if(toval[u]<toval[v]+val[u]){ pre[u]=v; toval[u]=toval[v]+val[u]; } } } } } } vector<int> get_path(int t){ vector<int>path; for(;t!=-1;t=pre[t]) path.push_back(t); reverse(path.begin(), path.end()); return path; } int N,M,S,D; int main(){ cin>>N>>M>>S>>D; V=N; for(int i=0;i<N;i++) cin>>val[i]; for(int i=0;i<V;i++){ for(int j=0;j<V;j++){ if(i!=j) cost[i][j]=cost[i][j]=inf; } } for(int i=0;i<M;i++){ int a,b,c; cin>>a>>b>>c; cost[a][b]=cost[b][a]=c; } dijkstra(S); printf("%d %d ",pathnum[D],toval[D]); vector<int>path=get_path(D); for(int i=0;i<path.size();i++){ printf("%d%c",path[i],i==path.size()-1?' ':' '); } return 0; }
2、按边存储 $O(nlogn)$
#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #include<iostream> #include<vector> #include<queue> #define max_v 502 #define inf 0x3f3f3f3f using namespace std; typedef long long ll; struct edge{ int to,cost; }; typedef pair<int,int>P;//按边存储，默认不可以自己到自己进行dp int V,pre[max_v],pathnum[max_v],val[max_v],toval[max_v]; vector<edge>G[max_v]; int d[max_v]; void dijkstra(int s){ priority_queue<P,vector<P>,greater<P> >que; fill(d,d+V,inf); fill(pre,pre+V,-1); toval[s]=val[s]; pathnum[s]=1; d[s]=0; que.push(P(0,s)); while(!que.empty()){ P p=que.top();que.pop(); int v=p.second; if(d[v]<p.first) continue; for(int i=0;i<G[v].size();i++){ edge e=G[v][i]; if(d[e.to]>d[v]+e.cost){ d[e.to]=d[v]+e.cost; pathnum[e.to]=pathnum[v]; toval[e.to]=toval[v]+val[e.to]; pre[e.to]=v; que.push(P(d[e.to],e.to)); }else if(d[e.to]==d[v]+e.cost){ pathnum[e.to]+=pathnum[v]; if(toval[e.to]<toval[v]+val[e.to]){ toval[e.to]=toval[v]+val[e.to]; pre[e.to]=v; } } } } } vector<int> get_path(int t){ vector<int>path; for(;t!=-1;t=pre[t]) path.push_back(t); reverse(path.begin(), path.end()); return path; } int N,M,S,D; int main(){ cin>>N>>M>>S>>D; V=N; for(int i=0;i<N;i++) cin>>val[i]; for(int i=0;i<M;i++){ int a,b,c; cin>>a>>b>>c; G[a].push_back((edge){b,c}); G[b].push_back((edge){a,c}); } dijkstra(S); printf("%d %d ",pathnum[D],toval[D]); vector<int>path=get_path(D); for(int i=0;i<path.size();i++){ printf("%d%c",path[i],i==path.size()-1?' ':' '); } return 0; }
3、代码三
#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<iostream> #include<cmath> #include<vector> #define inf 0x3f3f3f3f #define max_v 502 using namespace std; typedef long long ll; int pre[max_v],pathnum[max_v],toval[max_v],val[max_v]; int cost[max_v][max_v],d[max_v],used[max_v],V; void dijkstra(int s){ //边权和点权都是通过顶点体现 fill(d,d+V,inf); fill(used,used+V,0); fill(pre,pre+V,-1); d[s]=0; pathnum[s]=1; toval[s]=val[s]; while(true){ int v=-1; for(int u=0;u<V;u++){ if(!used[u]&&(v==-1||d[u]<d[v])) v=u; } if(v==-1) break; used[v]=true; for(int u=0;u<V;u++){ if(d[u]>d[v]+cost[v][u]){ d[u]=d[v]+cost[v][u]; pre[u]=v; pathnum[u]=pathnum[v]; toval[u]=toval[v]+val[u]; }else if(d[u]==d[v]+cost[v][u]){ pathnum[u]+=pathnum[v]; if(toval[u]<toval[v]+val[u]){ pre[u]=v; toval[u]=toval[v]+val[u]; } } } } } vector<int> get_path(int t){ vector<int>path; for(;t!=-1;t=pre[t]) path.push_back(t); reverse(path.begin(), path.end()); return path; } int N,M,S,D; int main(){ cin>>N>>M>>S>>D; V=N; for(int i=0;i<N;i++) cin>>val[i]; for(int i=0;i<V;i++){ for(int j=0;j<V;j++){ cost[i][j]=cost[i][j]=inf; } } for(int i=0;i<M;i++){ int a,b,c; cin>>a>>b>>c; cost[a][b]=cost[b][a]=c; } dijkstra(S); printf("%d %d ",pathnum[D],toval[D]); vector<int>path=get_path(D); for(int i=0;i<path.size();i++){ printf("%d%c",path[i],i==path.size()-1?' ':' '); } return 0; }