e810 - 2.潛水 (Diving)

🔗 前往 ZeroJudge 原題

題目描述

題目描述了小軒要從 A 島潛水到 B 島，需要找到最小容量的氧氣筒。給定 N 座島和 M 條潛水路徑，每條路徑有氧氣消耗量。小軒可以在每座島重新裝滿氧氣筒。要求輸出最小氧氣筒容量，如果無法到達則輸出 -1。

解題思路

本題可以使用 Floyd-Warshall 演算法來解決。Floyd-Warshall 演算法用於計算圖中所有頂點對之間的最小距離。在這個問題中，頂點代表島嶼，邊的權重代表潛水路徑的氧氣消耗量。

1. 初始化一個 N x N 的矩陣 dp，其中 dp[i][j] 表示從島 i 到島 j 的最小氧氣消耗量。如果 i 和 j 之間沒有直接路徑，則 dp[i][j] 初始化為 INT_MAX。如果 i 等於 j，則 dp[i][j] 初始化為 0。
2. 遍歷給定的 M 條潛水路徑，更新 dp 矩陣。
3. 使用 Floyd-Warshall 演算法，遍歷所有可能的中間島 k，更新 dp[i][j] 的值：dp[i][j] = min(max(dp[i][k], dp[k][j]), dp[i][j])。
4. 最後，輸出 dp[A][B] 的值。如果 dp[A][B] 仍然是 INT_MAX，則表示無法從 A 島到達 B 島，輸出 -1。

複雜度分析

• 時間複雜度: O(N^3)，其中 N 是島嶼的數量。Floyd-Warshall 演算法的時間複雜度為 O(N^3)。
• 空間複雜度: O(N^2)，用於儲存 dp 矩陣。

程式碼

#include <iostream>
#include <climits> 
using namespace std;
long long dp[550][550],n,m,v,x,y;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			dp[i][j]=INT_MAX;
			if(i==j)dp[i][j]=0;
		}
	} 
	for(int i=0;i<m;++i){
		cin >> x >> y >> v;
		dp[x][y]=dp[y][x]=min(dp[x][y],v);
	}
	for(int k=0;k<n;++k){
		for(int i=0;i<n;++i){
			for(int j=0;j<n;++j){
				dp[i][j]=min(max(dp[i][k],dp[k][j]),dp[i][j]);
			}
		}
	} 
	cin >> x >> y;
	if(dp[x][y]==INT_MAX){
		cout << "-1";
	}
	else{
		cout << dp[x][y];
	}
}