【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e810
【解題想法】BFS 找最小的路徑成本
- 每抵達一座島就可以把氧氣筒重新裝滿，希望氧氣筒的容量夠用就好
- 找出從起點到其它每一座島的路徑中，單段路徑需要花費的氧氣量的最大值。
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define INF 0x3F3F3F3F
vector <pii> g[505];
int vis[505];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, M, A, B, W;
cin >> N >> M;
for (int i=0; i<M; i++){
cin >> A >> B >> W;
g[A].push_back({B, W});
g[B].push_back({A, W});
}
cin >> A >> B;
memset(vis, 0x3F, sizeof(vis));
queue <int> q;
q.push(A);
vis[A] = 0;
while (!q.empty()){
int now = q.front(); q.pop();
for (auto nxt: g[now]){
int newDis = max(vis[now], nxt.S);
if (newDis < vis[nxt.F]){
vis[nxt.F] = newDis;
q.push(nxt.F);
}
}
}
if (vis[B] == INF) cout << "-1\n";
else cout << vis[B] << "\n";
}
Python code (credit: Amy Chou)
import sys
INF = 1000000000
for line in sys.stdin:
N, M = map(int, line.split())
g = [[] for _ in range(N)]
for _ in range(M):
A, B, W = map(int, sys.stdin.readline().split())
g[A].append((B, W))
g[B].append((A, W))
A, B = map(int, sys.stdin.readline().split())
vis = [INF for _ in range(N)]
vis[A] = 0
q = [A]
while q:
now = q.pop(0)
for nxt, W in g[now]:
nW = max(vis[now], W)
if nW < vis[nxt]:
vis[nxt] = nW
q.append(nxt)
if vis[B] == INF:
print(-1)
else:
print(vis[B])