# 【題解】POJ 1797 Heavy Transportation

【題目敘述】https://vjudge.net/problem/POJ-1797
【解題想法】Dijkstra + Minimax

```#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int t, Case, n, m, a, b, c, dis[1005], exp[1005];
struct r{
int x, w;
};
vector <r> v[1005];
r nxt;

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while (t--){
cin >> n >> m;
for (int i = 1; i <= n; i++){
v[i].clear();
}
for (int i = 0; i < m; i++){
cin >> a >> b >> c;
v[a].push_back({b, c});
v[b].push_back({a, c});
}
priority_queue <pair<int, int> > pq;
pq.push({1000005, 1});
memset(dis, -1, sizeof(dis));
memset(exp, 0, sizeof(exp));
dis[1] = 1000005;
pair <int, int> now;
while (!pq.empty()){
now = pq.top();
pq.pop();
if (exp[now.second]) continue;
exp[now.second] = 1;
for (int i = 0; i < v[now.second].size(); i++){
nxt = v[now.second][i];
if (min(dis[now.second], nxt.w) > dis[nxt.x]){
dis[nxt.x] = min(dis[now.second], nxt.w);
pq.push({dis[nxt.x], nxt.x});
}
}
}
Case++;
cout << "Scenario #" << Case << ":\n";
cout << dis[n] << "\n\n";
}
}
```