daily pastebin goal
54%
SHARE
TWEET

7C

a guest May 19th, 2017 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <set>
  3. #include <vector>
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9.     freopen("pathbgep.in", "r", stdin);
  10.     freopen("pathbgep.out", "w", stdout);
  11.     long long n, m;
  12.     const long long SIZE = 30000, INFINITY = (const long long int) 1e17;
  13.     scanf("%lld %lld", &n, &m);
  14.     vector<pair<int, int>> adjacencyLis[SIZE];
  15.     for (int i = 0; i < m; ++i) {
  16.         long long vertex1, vertex2, weight;
  17.         scanf("%lld %lld %lld", &vertex1, &vertex2, &weight);
  18.         adjacencyLis[vertex1 - 1].push_back({vertex2 - 1, weight});
  19.         adjacencyLis[vertex2 - 1].push_back({vertex1 - 1, weight});
  20.     }
  21.     vector<long long> d(n, INFINITY);
  22.     vector<bool> vst(n, false);
  23.     d[0] = 0;
  24.     set<pair<long long, long long>> s;
  25.     s.insert({0, 0});
  26.     for (int i = 0; i < n && s.size(); ++i) {
  27.         auto p = *s.begin();
  28.         long long int v = p.second;
  29.         s.erase(p);
  30.         vst[v] = true;
  31.         for (auto to: adjacencyLis[v]) {
  32.             if (d[to.first] > d[v] + to.second) {
  33.                 s.erase({d[to.first], to.first});
  34.                 d[to.first] = d[v] + to.second;
  35.                 s.insert({d[to.first], to.first});
  36.             }
  37.         }
  38.     }
  39.     for (int i = 0; i < n; ++i) {
  40.         printf("%lld ", d[i]);
  41.     }
  42.     return 0;
  43. }
RAW Paste Data
Top