PTA:7-112 旅遊規劃 (25分)(dfs,dijkstra）

7-112 旅遊規劃 (25分)

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

輸入格式:

輸入說明：輸入資料的第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

剛拿到題目，想的就是dfs進行搜尋，奈何最後怎麼都過不了最後一個測試點，就是一直逾時。

這裡附上dfs代碼，如果有大佬用的該方法，效率比較好的話，麻煩教教我，嘻嘻。

#include <bits/stdc++.h>
using namespace std;
int n,m,s,d;
vector<int> r[520]; 
int minl=1e9,minmo=1e9,suml,summo;
int len[520][520],mo[520][520],vis[520][520];

void dsf(int x, int y){
	if(y==d){
		if(suml+len[x][y]<minl||(suml+len[x][y]==minl&&summo+mo[x][y]<minmo)){
			minl=suml+len[x][y];
			minmo=summo+mo[x][y];
			return;
		}		
	}
	vis[x][y]=1;
	vis[y][x]=1;
	suml += len[x][y];
	summo += mo[x][y];
	for(int i=0; i<r[y].size(); i++){
		if(!vis[y][r[y][i]]&&suml+len[y][r[y][i]]<=minl){
			dsf(y,r[y][i]);
		}
	}
	vis[x][y]=0;
	vis[y][x]=0;
	suml -= len[x][y];
	summo -= mo[x][y];
	return;
}

int main(){
	cin>>n>>m>>s>>d;
	scanf("%d%d%d%d",&n,&m,&s,&d);
	while(m--){
		 int a,b,c,d;
		 cin>>a>>b>>c>>d;
		 r[a].push_back(b);
		 r[b].push_back(a);
		 len[a][b]=c;
		 len[b][a]=c;
		 mo[a][b]=d;
		 mo[b][a]=d; 
	} 
	for(int i=0; i<r[s].size(); i++){
		if(!vis[s][r[s][i]]&&suml+len[s][r[s][i]]<=minl){
			suml = 0;
			summo = 0;
			dsf(s,r[s][i]);
		}
	}
	cout<<minl<<" "<<minmo<<endl;
	return 0;
} 

           

下面是AC代碼，用的是dijkstra的方法，會快一些，（好像用堆來優化更快），最後通過所有測試點：

（PS：該處代碼參考https://www.cnblogs.com/FrankChen831X/p/10492723.html）

#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;
    }
    //dis[i]起點到各結點的距離 
    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;
}
           

總結：

1.循環找出距離起點最近的點，并标記其已被通路；如果未找到點則搜尋結束。

2.在1的基礎上，已經到找到距離起點最近的點，從該點開始出發，判斷該點到其他點的距離。如果起點到其他點的距離大于了經過最近點再到其他點的距離，更新其他點到起點的距離。

3.通過循環n次也就知道了所有點距離起點的最近距離了。

歡迎大家批評改正！！！