点击打开pat链接
#include<iostream> #include<math.h> #include<algorithm> #include<queue> #include<map> #include<set> #include<stack> #include<string> #include<vector> using namespace std; #define INF 100000000 #define maxn 100010 struct highway{ int end; int distance; int cost; }; vector<highway> ad[maxn]; bool visit[maxn]={false}; int cost[maxn]={0}; int dis[maxn]; int pre[maxn]; void dij(int s,int city){ fill(dis,dis+city,INF); fill(cost,cost+city,INF);//注意边的初始化的特点 dis[s]=0; cost[s]=0; for(int i=0;i<city;i++) {pre[i]=i; }//注意pre的初始化 for(int i=0;i<city;i++) { int store=-1,min=INF; for(int j=0;j<city;j++) { if(visit[j]==false) { if(dis[j]<min) { store=j; min=dis[j]; } } } if(store==-1) return; visit[store]=true; for(int k=0;k<ad[store].size();k++){ int end=ad[store][k].end; // cout<<end<<endl; if(visit[end]==false) { int qw=dis[store]+ad[store][k].distance; if(dis[end]>qw) { dis[end]=qw; cost[end]=cost[store]+ad[store][k].cost; pre[end]=store; } else if(dis[end]==qw) { if(cost[end]>cost[store]+ad[store][k].cost) { cost[end]=cost[store]+ad[store][k].cost; pre[end]=store; } } } } } } void DFS(int v,int s)//打印 { if(v==s){ cout<<s<<" "; return; } DFS(pre[v],s); cout<<v<<" "; } int main() { int city,hnum,st,ed; cin>>city>>hnum>>st>>ed; for(int i=0;i<hnum;i++) { int start,end,distance,cost; cin>>start>>end>>distance>>cost; highway temp; temp.end=end,temp.distance=distance,temp.cost=cost; ad[start].push_back(temp); temp.end=start; ad[end].push_back(temp); } dij(st,city); DFS(ed,st); cout<<dis[ed]<<" "<<cost[ed]; return 0; }
