【題解】POJ 1797 Heavy Transportation

#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";
    }
}