Advertisement
Josif_tepe

Untitled

May 11th, 2021
229
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.72 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <vector>
  6. using namespace std;
  7.  
  8.  
  9. struct node {
  10.     int idx;
  11.     int distance;
  12.    
  13.     node() {}
  14.     node(int _idx, int _distance) {
  15.         idx = _idx;
  16.         distance = _distance;
  17.     }
  18.    
  19.     bool operator < (const node &tmp) const {
  20.         return distance > tmp.distance;
  21.     }
  22.    
  23. };
  24. int main() {
  25.     int n; // broj na teminja
  26.     int m; // brojot na rebra
  27.     cin >> n >> m;
  28.    
  29.     vector<pair<int, int> > graph[n + 1];
  30.     for(int i = 0; i < m; i++) {
  31.         int a, b, c; // povrzani se teminjata a i b so distanca c
  32.         cin >> a >> b >> c;
  33.         graph[a].push_back(make_pair(b, c));
  34.         graph[b].push_back(make_pair(a, c));
  35.     }
  36.    
  37.     int S, E;
  38.     // S --> pocetno teme
  39.     // E --> krajno teme
  40.     cin >> S >> E;
  41.    
  42.     priority_queue<node> pq;
  43.     pq.push(node(S, 0)); // prviot element vo priority queue
  44.    
  45.     bool visited[n + 1];
  46.     int dist[n + 1];
  47.     for(int i = 0; i < n; i++) {
  48.         visited[i] = false;
  49.         dist[i] = 2000000000;
  50.     }
  51.     dist[S] = 0;
  52.     while(!pq.empty()) {
  53.         node c = pq.top();
  54.         pq.pop();
  55.        
  56.         visited[c.idx] = true;
  57.        
  58.         for(int i = 0; i < graph[c.idx].size(); i++) {
  59.             int sosed = graph[c.idx][i].first;
  60.             int rebro = graph[c.idx][i].second;
  61.             if(!visited[sosed] and c.distance + rebro < dist[sosed]) {
  62.                 dist[sosed] = c.distance + rebro;
  63.                 pq.push(node(sosed, c.distance + rebro));
  64.             }
  65.         }
  66.     }
  67.     for(int i = 0; i < n; i++) {
  68.         cout << S << " --> " << i << " " << dist[i] << endl;
  69.     }
  70.    
  71.     return 0;
  72. }
  73.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement