题目链接：点击打开链接
题目大意：略。
解题思路：AC1 代码 和 AC2 代码（推荐）的区别在于：代码1的初始化为 mem(dis,0) 在进入 for(int i=1;i<n-1;i++) 之前已经初始化好 第一个 s 的更新；而代码2的初始化为 mem(dis,INF) 在进入 while(1) 之前没有进行第一个 s 的更新，而是把这个操作放在 while(1) 里面，这样就可以把第一个 s 赋值给 pre[] 数组。即：代码2中第一个 s 的更新工作其实就是代码1进入 for(int i=1;i<n-1;i++) 之前的更新工作，只是为了更新第一个 pre[]=s 而已。
AC1 代码（常规版）
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define ssclr(ss) ss.clear(), ss.str("") #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; const int maxn=510; int n,m,s,d; int mp[maxn][maxn], cost[maxn][maxn]; int vis[maxn], dis[maxn], cst[maxn], pre[maxn]; vector<int> vec; void init() { mem(vis,0), mem(cst,0), mem(dis,0), mem(pre,-1); mem(mp,INF), mem(cost,INF); } int dijkstra(int s) { for(int i=0;i<n;i++) { dis[i]=mp[s][i]; cst[i]=cost[s][i]; } vis[s]=1, dis[s]=0; for(int i=1;i<n-1;i++) { int v=-1, mi=INF; for(int j=0;j<n;j++) { if(!vis[j] && dis[j]<mi) mi=dis[j], v=j; } if(v==-1) return 0; vis[v]=1; for(int j=0;j<n;j++) { if(!vis[j] && mi+mp[v][j]<dis[j]) { pre[j]=v; dis[j]=mi+mp[v][j]; cst[j]=cst[v]+cost[v][j]; } else if(!vis[j] && mi+mp[v][j]==dis[j] && cst[j]>cst[v]+cost[v][j]) cst[j]=cst[v]+cost[v][j], pre[j]=v; } } } int main() { init(); int a,b,u,v; scanf("%d%d%d%d",&n,&m,&s,&d); for(int i=0;i<m;i++) { scanf("%d%d%d%d",&u,&v,&a,&b); mp[u][v]=mp[v][u]=a; cost[u][v]=cost[v][u]=b; } if(dijkstra(s)) { vec.clear(); int h=d; while(h!=-1) { vec.push_back(h); h=pre[h]; } printf("%d ",s); for(int i=vec.size()-1;i>=0;i--) printf("%d ",vec[i]); printf("%d %d\n",dis[d],cst[d]); } else puts("-1"); return 0; }
AC2 代码（简化版）
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define ssclr(ss) ss.clear(), ss.str("") #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; const int maxn=510; int n,m,s,d; int mp[maxn][maxn], cost[maxn][maxn]; int vis[maxn], dis[maxn], cst[maxn], pre[maxn]; vector<int> vec; void init() { mem(vis,0), mem(cst,0), mem(dis,INF), mem(pre,-1); mem(mp,INF), mem(cost,INF); } int dijkstra(int s) { dis[s]=0; while(1) { int mi=INF,s=-1; for(int j=0;j<n;j++) { if(!vis[j] && dis[j]<mi) mi=dis[j], s=j; } if(s==d) return 1; if ( s==-1 ) return 0; vis[s] = 1; for(int j=0;j<n;j++) { if(!vis[j] && mi+mp[s][j]<dis[j]) { pre[j]=s; dis[j]=mi+mp[s][j]; cst[j]=cst[s]+cost[s][j]; } else if(!vis[j] && mi+mp[s][j]==dis[j] && cst[j]>cst[s]+cost[s][j]) cst[j]=cst[s]+cost[s][j], pre[j]=s; } } } int main() { init(); int a,b,u,v; scanf("%d%d%d%d",&n,&m,&s,&d); for(int i=0;i<m;i++) { scanf("%d%d%d%d",&u,&v,&a,&b); mp[u][v]=mp[v][u]=a; cost[u][v]=cost[v][u]=b; } if(dijkstra(s)) { vec.clear(); int h=d; while(h!=-1) { vec.push_back(h); h=pre[h]; } for(int i=vec.size()-1;i>=0;i--) printf("%d ",vec[i]); printf("%d %d\n",dis[d],cst[d]); } else puts("-1"); return 0; }
