a874 - 14. Trace Route

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算一個給定網路中，從起點到終點的最短路徑長度。網路由多個節點（電腦）和邊（電纜）組成，每條邊都有一個權重（傳輸時間）。如果起點和終點之間沒有路徑，則輸出 "NoRoute"。

解題思路

本題可以使用 Floyd-Warshall 演算法來解決。Floyd-Warshall 演算法是一種用於計算圖中所有頂點對之間最短路徑的演算法。它通過迭代更新所有可能的頂點對之間的距離，最終得到所有頂點對之間的最短路徑長度。

具體步驟如下：

1. 初始化距離矩陣：將所有頂點對之間的距離初始化為無限大（在本程式碼中，使用 0x3f 表示）。對於直接相連的頂點對，將距離初始化為給定的權重。
2. 迭代更新距離矩陣：對於每個中間頂點 k，檢查是否通過 k 可以縮短從頂點 i 到頂點 j 的距離。如果 dist[i][j] > dist[i][k] + dist[k][j]，則更新 dist[i][j] 為 dist[i][k] + dist[k][j]。
3. 輸出結果：計算完成後，查詢起點和終點之間的距離。如果距離仍然是無限大，則輸出 "NoRoute"，否則輸出最短路徑長度。

複雜度分析

• 時間複雜度: O(n^3)，其中 n 是頂點的數量。Floyd-Warshall 演算法需要三重迴圈來迭代更新距離矩陣。
• 空間複雜度: O(n^2)，其中 n 是頂點的數量。需要一個 n x n 的矩陣來存儲距離。

程式碼

#include <bits/stdc++.h> 
using namespace std;
int n,e[26][26],v;
char x,y;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> n){
		memset(e,0x3f,sizeof(e));
		for(int i=0;i<n;++i){
			cin >> x >> y >> v;
			x-='A';
			y-='A';
			e[x][y]=e[y][x]=min(e[x][y],v);
		}
		for(int k=0;k<26;++k)
			for(int i=0;i<26;++i)
				for(int j=0;j<26;++j)
					e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
		cin >> x >> y;
		x-='A';
		y-='A';
		if(x==y){
			cout << "0\n";
		}
		else{
			if(e[x][y]>1e6)cout << "NoRoute\n";
			else cout << e[x][y] << "\n";
		} 
	}
}