Advertisement
Josif_tepe

Untitled

Jan 25th, 2022
692
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5. using namespace std;
  6. struct node {
  7.     int idx;
  8.     int cost;
  9.    
  10.     node(){}
  11.     node(int _idx, int _cost) {
  12.         idx = _idx;
  13.         cost = _cost;
  14.     }
  15.     bool operator < (const node &tmp) const {
  16.         return cost > tmp.cost;
  17.     }
  18. };
  19. int main() {
  20.    
  21.     int n, m;
  22.     cin >> n >> m;
  23.     vector<pair<int, int> > graph[n + 1];
  24.     for(int i = 0; i < m; i++) {
  25.         int a, b, c;
  26.         cin >> a >> b >> c;
  27.         graph[a].push_back(make_pair(b, c));
  28.         graph[b].push_back(make_pair(a, c));
  29.     }
  30.    
  31.     int S, E;
  32.     cin >> S >> E;
  33.    
  34.     priority_queue<node> pq;
  35.     pq.push(node(S, 0));
  36.     vector<bool> visited(n + 1, false);
  37.     vector<int> distance(n + 1, 2e9);
  38.    
  39.     distance[S] = 0; // start
  40.    
  41.     while(!pq.empty()) {
  42.         node current_node = pq.top();
  43.         pq.pop();
  44.         visited[current_node.idx] = true;
  45.         for(int i = 0; i < graph[current_node.idx].size(); i++) {
  46.             int sosed = graph[current_node.idx][i].first;
  47.             int rebro = graph[current_node.idx][i].second;
  48.             if(!visited[sosed] and current_node.cost + rebro < distance[sosed]) {
  49.                 pq.push(node(sosed, current_node.cost + rebro));
  50.                 distance[sosed] = current_node.cost + rebro;
  51.             }
  52.         }
  53.     }
  54.     cout << distance[E] << endl; // end
  55.     return 0;
  56. }
  57.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement