SHARE
TWEET

Untitled

a guest Feb 5th, 2020 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define int li
  2.  
  3. struct Edge {
  4.   int to, cost;
  5. };
  6.  
  7. void solve(__attribute__((unused)) bool read) {
  8.   int n, m;
  9.   cin >> n >> m;
  10.   vector<vector<Edge>> g(n);
  11.   for (int i = 0; i < m; ++i) {
  12.     int a, b, cost;
  13.     cin >> a >> b >> cost;
  14.     --a; --b;
  15.     g[a].push_back({b, cost});
  16.     g[b].push_back({a, cost});
  17.   }
  18.   priority_queue<pair<int, int>> q;
  19.   const int INF = (int)1e18;
  20.   vector<int> dist(n, INF);
  21.   dist[0] = 0;
  22.   q.push({0, 0});
  23.   vector<char> used(n, false);
  24.   while (!q.empty()) {
  25.     int v = q.top().second;
  26.     q.pop();
  27.     if (used[v]) {
  28.       continue;
  29.     }
  30.     used[v] = true;
  31.     for (auto e : g[v]) {
  32.       int candy = e.cost + dist[v];
  33.       if (candy < dist[e.to]) {
  34.         dist[e.to] = candy;
  35.         q.push({dist[e.to], e.to});
  36.       }
  37.     }
  38.   }
  39.   int res = dist[n - 1];
  40.   if (res == INF) {
  41.     res = -1;
  42.   }
  43.   cout << res << "\n";
  44. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top