Fshl0

Dijkstra

Jan 19th, 2021
91
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. vector <pair<int, int> > adj[MX];
  2. priority_queue <pii, vector<pii >, greater<pii> > pq;
  3.  
  4. ll dist[MX];
  5. int pa[MX];
  6.  
  7. void test_case() {
  8.     int n, m;
  9.     cin >> n >> m;
  10.     while (m--) {
  11.         int u, v, w;
  12.         scanf("%d %d %d", &u, &v, &w);
  13.         adj[u].pb({v, w});
  14.         adj[v].pb({u, w});
  15.     }
  16.     for (int i = 1; i <= n; i++)
  17.         dist[i] = inf;
  18.     dist[1] = 0;
  19.     pq.push({0, 1});
  20.     while (!pq.empty()) {
  21.         pair <ll, int> v = pq.top();
  22.         pq.pop();
  23.         if (v.F != dist[v.S]) continue;
  24.         for (auto edge: adj[v.S]) {
  25.             int to = edge.F, len = edge.S;
  26.             if (dist[v.S] + len < dist[to]) {
  27.                 dist[to] = dist[v.S] + len;
  28.                 pa[to] = v.S;
  29.                 pq.push({dist[to], to});
  30.             }
  31.         }
  32.     }
  33.     if (dist[n] == inf) {
  34.         cout << -1 << endl;
  35.         return;
  36.     }
  37.     vector <int> res;
  38.     while (n != 1) {
  39.         res.pb(n);
  40.         n = pa[n];
  41.     }
  42.     res.pb(1);
  43.     reverse(res.begin(), res.end());
  44.     for (auto u: res)
  45.         printf("%d ", u);
  46.     cout << "\n";
  47.     return;
  48. }
RAW Paste Data