有了一張自駕旅游路線圖，你會知道城市間的高速公路長度、以及該公路要收取的過路費。現在需要你寫一個程序，幫助前來咨詢的游客找一條出發地和目的地之間的最短路徑。如果有若干條路徑都是最短的，那么需要輸出最便宜的一條路徑。

輸入格式:

輸入說明：輸入數據的第1行給出4個正整數N、M、S、D，其中N（2≤N≤500）是城市的個數，順便假設城市的編號為0~(N?1)；M是高速公路的條數；S是出發地的城市編號；D是目的地的城市編號。隨后的M行中，每行給出一條高速公路的信息，分別是：城市1、城市2、高速公路長度、收費額，中間用空格分開，數字均為整數且不超過500。輸入保證解的存在。

輸出格式:

在一行里輸出路徑的長度和收費總額，數字間以空格分隔，輸出結尾不能有多余空格。

輸入樣例:

4 5 0 3 0 1 1 20 1 3 2 30 0 3 4 10 0 2 2 20 2 3 1 20

輸出樣例:

3 40

題解:Dijsktra求解，然后多一個當路徑相等時，按價格小的來

代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define INF 0x3f3f3fusing namespace std;int Map[505][505]; int Cost[505][505]; int dis[505],MCost[505]; bool vis[505]= {false}; int Min; void Dijkstra(int v0,int v,int d) {dis[v0]=0;vis[v0]=true;for(int i=0; i<v; i++) {Min=INF;for(int k=0; k<v; k++) {if(!vis[k]) {if(dis[k]<Min) {Min=dis[k];v0=k;}}}vis[v0]=true;for(int k=0; k<v; k++) {if(!vis[k]&&Min+Map[v0][k]<dis[k]) {dis[k]=Min+Map[v0][k];MCost[k]=MCost[v0]+Cost[v0][k];} else if(!vis[k]&&Min+Map[v0][k]==dis[k]&&MCost[k]>MCost[v0]+Cost[v0][k]) {MCost[k]=MCost[v0]+Cost[v0][k];}}} } int main() {int v,e,s,d;scanf("%d %d %d %d",&v,&e,&s,&d);for(int i=0; i<v; i++)for(int j=0; j<v; j++) {Map[i][j]=Map[j][i]=INF;Cost[i][j]=Cost[j][i]=INF;//設置為雙向連通,并初始化為最大值}for(int i=0; i<e; i++) {int a,b,c,d;cin>>a>>b>>c>>d;Map[a][b]=Map[b][a]=c;Cost[a][b]=Cost[b][a]=d;}for(int i=0; i<v; i++) {dis[i]=Map[i][s];//Map[i][s]為點i到起始點的距離MCost[i]=Cost[i][s];}Dijkstra(s,v,d);cout<<dis[d]<<" "<<MCost[d]<<endl;return 0; }

?

轉載于:https://www.cnblogs.com/Staceyacm/p/10781881.html

總結

以上是生活随笔為你收集整理的7-36 旅游规划 （25 分(Dijkstra)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。