题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805464397627392 题目思路：套dijsktra算法思路同时在合适条件下优化即可； 代码：
# include<stdio.h> # include<math.h> # include<algorithm> using namespace std; const int inf=99999999; bool vis[510]; int d[510],cost[510][510],g[510][510],sum[510],pre[510]; int n,m,start,end1; void dijsktra(){ fill(d,d+510,inf); fill(sum,sum+510,inf); int i,u,min; d[start]=0; sum[start]=0; for(i=0;i<n;i++){ u=-1,min=inf; for(int j=0;j<n;j++){ if(d[j]<min&&vis[j]==false){ min=d[j]; u=j; } } vis[u]=true; if(u==-1) return; for(int v=0;v<n;v++){ if(g[u][v]!=inf&&vis[v]==false){ if(d[u]+g[u][v]<d[v]){ d[v]=d[u]+g[u][v]; sum[v]=sum[u]+cost[u][v]; pre[v]=u; } else if(d[u]+g[u][v]==d[v]&&cost[u][v]+sum[u]<sum[v]){ sum[v]=sum[u]+cost[u][v]; pre[v]=u; } } } } } void dfs(int a){ if(a==start) return; dfs(pre[a]); printf("%d ",a); } int main(){ fill(g[0],g[0]+510*510,inf); fill(cost[0],cost[0]+510*510,inf); fill(vis,vis+510,0); scanf("%d %d %d %d",&n,&m,&start,&end1); int i; for(i=0;i<m;i++){ int a,b; scanf("%d %d ",&a,&b); scanf("%d %d",&g[a][b],&cost[a][b]); g[b][a]=g[a][b]; cost[b][a]=cost[a][b]; } dijsktra(); printf("%d ",start); dfs(end1); printf("%d ",d[end1]); printf("%d",sum[end1]); return 0; }