LightOJ - Brush (V)

#include <bits/stdc++.h>
using namespace std;

const int maxN = 110;
vector<pair<int,int>> adj[maxN];
int dist[maxN];

void dijkstra (int n) {
    for (int i = 1; i <= n; ++i) dist[i] = (int) 1e7;
    priority_queue<pair<int,int>> pq;
    dist[1] = 0;
    pq.push(make_pair(0,1));
    while (!pq.empty()) {
        int node = pq.top().second;
        int cost = abs(pq.top().first);
        pq.pop();
        if (dist[node] < cost) continue;
        for (pair<int,int> child : adj[node]) {
            if (dist[child.first] > cost + child.second) {
                dist[child.first] = cost + child.second;
                pq.push(make_pair(-dist[child.first],child.first));
            }
        }
    }
}

int main () {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
     int T;
     cin >> T;
     for (int test_case = 1; test_case <= T; ++test_case) {
         int n,m;
         cin >> n >> m;
         for (int i = 1; i <= n; ++i) adj[i].clear();
         int node_cost[maxN][maxN];
         for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) node_cost[i][j] = (i == j ? 0 : (int) 1e7);
         for (int i = 1; i <= m; ++i) {
             int u,v,cost;
             cin >> u >> v >> cost;
             node_cost[u][v] = min(node_cost[u][v],cost);
             node_cost[v][u] = min(node_cost[v][u],cost);
         }
         for (int i = 1; i <= n; ++i) {
             for (int j = 1; j <= n; ++j) {
                 if (i != j and node_cost[i][j] != (int) 1e7) adj[i].push_back(make_pair(j,node_cost[i][j])),adj[j].push_back(make_pair(i,node_cost[i][j]));
             }
         }
         dijkstra(n);
         cout << "Case " << test_case << ": " << (dist[n] == (int) 1e7 ? "Impossible" : to_string(dist[n])) << '\n';
     }
     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}