d908 - 4. 最佳路徑
題目描述
題目要求在一個有向圖中，找到從指定起始節點出發，權重總和最大的路徑。圖由節點和有向邊組成，每條邊都有一個權重。
解題思路
本題可以使用 Floyd-Warshall 演算法來解決。Floyd-Warshall 演算法可以計算圖中所有節點對之間的 shortest paths (最短路徑)，但在此題目中，我們需要的是最長路徑，因此在初始化時，將所有距離設為負無窮大，然後將邊的權重取最大值。
具體步驟如下：
- 讀取起始節點和邊的數量。
- 建立一個鄰接矩陣
a，用於儲存邊的權重。 - 讀取每一條邊的資訊，並更新鄰接矩陣。
- 使用 Floyd-Warshall 演算法計算所有節點對之間的最長路徑。
- 找到從起始節點出發的最長路徑的權重。
- 輸出最長路徑的權重。
複雜度分析
- 時間複雜度: O(N^3)，其中 N 是節點的數量。Floyd-Warshall 演算法的時間複雜度為 O(V^3)，其中 V 是頂點數。
- 空間複雜度: O(N^2)，用於儲存鄰接矩陣。
程式碼
#include <iostream>
using namespace std;
int a[27][27],n,m,v;
char x,y,c;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> c >> n){
m=0;
for(int i=0;i<27;++i)
for(int j=0;j<27;++j)
a[i][j]=0;
for(int i=0;i<n;++i){
cin >> x >> y >> v;
a[x-'A'][y-'A']=max(v,a[x-'A'][y-'A']);
}
for(int k=0;k<27;++k)
for(int i=0;i<27;++i)
for(int j=0;j<27;++j)
if(a[i][k]&&a[k][j]&&i!=j)a[i][j]=max(a[i][j],a[i][k]+a[k][j]);
for(int i=0;i<27;++i)
m=max(a[c-'A'][i],m);
cout << m << "\n";
}
}