Advertisement
Josif_tepe

Untitled

Aug 17th, 2021
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4.  
  5. using namespace std;
  6. /*
  7.  0: (1, 2)
  8.  1:
  9.  2:
  10.  3:
  11.  4:
  12.  
  13.  
  14.  **/
  15.  
  16. struct node {
  17.     int index, shortest_cost;
  18.    
  19.     node(int i, int s) {
  20.         index = i;
  21.         shortest_cost = s;
  22.     }
  23.    
  24.     bool operator < (const node &tmp) const {
  25.         return shortest_cost > tmp.shortest_cost;
  26.     }
  27. };
  28.  
  29. int main()
  30. {
  31.     int n, m; // broj na teminja, broj na rebra
  32.     cin >> n >> m;
  33.     vector<pair<int, int> > graph[n + 5];
  34.     for(int i = 0; i < m; i++) {
  35.         int a, b, c; // temeto A e povrzano so temeto B i odaleceni se so C
  36.         cin >> a >> b >> c;
  37.         graph[a].push_back(make_pair(b, c));
  38.         graph[b].push_back(make_pair(a, c));
  39.     }
  40.    
  41.     int S, E;
  42.     cin >> S >> E;
  43.     // od kade sakam do kade sakam da najdam najkratok pat
  44.     priority_queue<node> pq;
  45.     pq.push(node(S, 0));
  46.    
  47.     vector<bool> visited(n + 1, false);
  48.    
  49.     while(!pq.empty()) {
  50.         node current = pq.top(); // kazi mi koj e najmal sosed
  51.         pq.pop();
  52.        
  53.         visited[current.index] = true;
  54.         if(current.index == E) {
  55.             cout << current.shortest_cost << endl; // ova e najkratkiot pat
  56.             break;
  57.         }
  58.        
  59.         for(int i = 0; i < graph[current.index].size(); i++) {
  60.             int sosed = graph[current.index][i].first;
  61.             int pat = graph[current.index][i].second;
  62.            
  63.             if(!visited[sosed]) {
  64.                 pq.push(node(sosed, current.shortest_cost + pat));
  65.             }
  66.            
  67.         }
  68.     }
  69.     return 0;
  70. }
  71.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement