題目鏈接：https://pintia.cn/problem-sets/1101307589335527424/problems/1101314114762387456
題意：給n給城市，m條公路，公路是雙向的，起點S，終點D，并給出每條公路連接的兩個city的編號以及路費，求S到D的最短距離，若具有最短距離的路線不止一條，求出路費最少的一條。
思路：單源最短路徑問題，利用dijkstra算法求出S到其他點的最短路徑，只不過加一個路費cost，在dis相等的情況下，取cost最小值。
AC代碼：
#include<bits/stdc++.h> using namespace std;const int inf=0x3f3f3f3f; int n,m,S,D; int dis[505],cost[505],a[505][505],b[505][505],vis[505];void dijkstra(){vis[S]=1;for(int i=0;i<n-1;++i){int Min=inf,k;for(int i=0;i<n;++i)if(!vis[i]&&dis[i]<Min)Min=dis[i],k=i;if(Min==inf) break;vis[k]=1;for(int i=0;i<n;++i)if(!vis[i]&&dis[i]>dis[k]+a[k][i]){dis[i]=dis[k]+a[k][i];cost[i]=cost[k]+b[k][i];}else if(!vis[i]&&dis[i]==dis[k]+a[k][i]&&cost[i]>cost[k]+b[k][i])cost[i]=cost[k]+b[k][i];} }int main(){scanf("%d%d%d%d",&n,&m,&S,&D);for(int i=0;i<n;++i)for(int j=0;j<n;++j)a[i][j]=b[i][j]=inf;int t1,t2,t3,t4;while(m--){scanf("%d%d%d%d",&t1,&t2,&t3,&t4);a[t1][t2]=a[t2][t1]=t3;b[t1][t2]=b[t2][t1]=t4;}for(int i=0;i<n;++i)dis[i]=a[S][i],cost[i]=b[S][i];dis[S]=cost[S]=0;dijkstra();printf("%d %d\n",dis[D],cost[D]);return 0; }
?
