Advertisement
Rentib

Dijkstra

Feb 14th, 2020
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.69 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.   long long n, m, dist, v;
  5.   cin >> n >> m;
  6.   vector<pair<long long, long long>> G[n + 1];
  7.   vector<long long> odl(n + 1, LLONG_MAX);
  8.   for(long long i = 0, a, b, c;i < m;i++){
  9.     cin >> a >> b >> c;
  10.     G[b].emplace_back(a, c);
  11.   }
  12.   priority_queue<pair<long long, long long>> q;
  13.   q.emplace(0, 1);
  14.   while(!q.empty()){
  15.     tie(dist, v) = q.top();
  16.     q.pop();
  17.     if(-dist > odl[v])
  18.       continue;
  19.     odl[v] = -dist;
  20.     for(auto i : G[v])
  21.       q.emplace(dist - i.second, i.first);
  22.   }
  23.   for(int i = 1;i <= n;i++){
  24.     if(odl[i] == LLONG_MAX)
  25.       cout << "+oo\n";
  26.     else
  27.       cout << odl[i] << '\n';
  28.   }
  29. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement