daily pastebin goal
12%
SHARE
TWEET

Untitled

a guest Jan 23rd, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <vector>
  3. #include <queue>
  4. #include <climits>
  5.  
  6. using namespace std;
  7.  
  8. ifstream inf("dijkstra2.in");
  9. ofstream outf("dijkstra2.out");
  10.  
  11.  
  12. priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
  13.  
  14. vector< pair<int, int> > ad[100001];
  15.  
  16. int dist[100001];
  17.  
  18. void Dijkstra(int start) {
  19.     pq.push(make_pair(0, start));
  20.     dist[start] = 0;
  21.  
  22.     while(!pq.empty()) {
  23.         int x = pq.top().second;
  24.         pq.pop();
  25.  
  26.         for(auto& el : ad[x]) {
  27.             if(dist[el.second] > dist[x] + el.first) {
  28.                 dist[el.second] = dist[x] + el.first;
  29.                 pq.push(make_pair(dist[el.second], el.second));
  30.             }
  31.         }
  32.     }
  33. }
  34.  
  35. int main() {
  36.     int n, p, x, y, c, m;
  37.     inf >> n >> m >> p;
  38.     while(m) {
  39.         inf >> x >> y >> c;
  40.         ad[x].push_back(make_pair(c, y));
  41.         ad[y].push_back(make_pair(c, x));
  42.         m--;
  43.     }
  44.     for(int i = 1; i <= n; i++) {
  45.         dist[i] = INT_MAX;
  46.     }
  47.     Dijkstra(p);
  48.     for(int i = 1; i <= n; i++) {
  49.         if(dist[i] != INT_MAX) {
  50.             outf << dist[i] << ' ';
  51.         }
  52.         else {
  53.             outf << "-1 ";
  54.         }
  55.     }
  56.     return 0;
  57. }
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