模板题
最短路+输出路径
如果最短路不唯一，输出cost最小的
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> #include <cmath> #include <queue> #define INF 0x3f3f3f3f using namespace std; const int maxn=505; int n,m,s,t; struct Edge{ int to; int next; int dis; int cost; }edge[maxn*maxn]; int head[maxn]; int tot; void init(){ memset(head,-1,sizeof(head)); tot=0; } void add(int u,int v,int d,int cc){ edge[tot].to=v; edge[tot].dis=d; edge[tot].cost=cc; edge[tot].next=head[u]; head[u]=tot++; } struct Node{ int u; int dis; int cost; bool operator<(const Node tmp)const{ if(dis==tmp.dis){ return cost>tmp.cost; } else{ return dis>tmp.dis; } } }; int dis[maxn]; int pre[maxn]; int vis[maxn]; int costs[maxn]; void dijkstra(int s,int t){ for(int i=0;i<n;i++){ dis[i]=INF; costs[i]=INF; pre[i]=-1; vis[i]=0; } priority_queue<Node>q; Node tmp,node; tmp.u=s; tmp.dis=0; tmp.cost=0; dis[s]=costs[s]=0; q.push(tmp); while(!q.empty()){ tmp=q.top(); q.pop(); int u=tmp.u; vis[u]=1; for(int k=head[u];k!=-1;k=edge[k].next){ int v=edge[k].to; if(!vis[v]){ if(tmp.dis+edge[k].dis<dis[v]){ dis[v]=tmp.dis+edge[k].dis; costs[v]=tmp.cost+edge[k].cost; node.u=v; node.dis=dis[v]; node.cost=costs[v]; q.push(node); pre[v]=u; } else if(tmp.dis+edge[k].dis==dis[v] && tmp.cost+edge[k].cost<costs[v]){ costs[v]=tmp.cost+edge[k].cost; node.u=v; node.dis=dis[v]; node.cost=costs[v]; q.push(node); pre[v]=u; } } } } } int main() { scanf("%d %d %d %d",&n,&m,&s,&t); int u,v,d,cc; init(); for(int i=0;i<m;i++){ scanf("%d %d %d %d",&u,&v,&d,&cc); add(u,v,d,cc); add(v,u,d,cc); } dijkstra(s,t); int route[maxn]; int cnt=0; int id=t; route[cnt++]=t; while(pre[id]!=-1){ id=pre[id]; route[cnt++]=id; } printf("%d",route[cnt-1]); for(int i=cnt-2;i>=0;i--){ printf(" %d",route[i]); } printf(" %d %d ",dis[t],costs[t]); return 0; }