Advertisement
Josif_tepe

Untitled

Jan 24th, 2025
33
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.67 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. const int maxn = 100005;
  7. const int INF = 2e9;
  8. vector<pair<int, int>> graph[maxn];
  9. int n;
  10.  
  11. struct node {
  12.     int idx, shortest_path;
  13.    
  14.     node() {}
  15.     node(int _idx, int _shortest_path) {
  16.         idx = _idx;
  17.         shortest_path = _shortest_path;
  18.     }
  19.     bool operator < (const node & tmp) const {
  20.         return shortest_path > tmp.shortest_path;
  21.     }
  22.    
  23. };
  24. int main()
  25. {
  26.    
  27.     cin >> n;
  28.     int m;
  29.     cin >> m;
  30.    
  31.     for(int i = 0; i < m; i++) {
  32.         int a, b, c;
  33.         cin >> a >> b >> c;
  34.         graph[a].push_back(make_pair(b, c));
  35.         graph[b].push_back(make_pair(a, c));
  36.     }
  37.     int S, E;
  38.     cin >> S >> E;
  39.    
  40.     vector<bool> visited(n, false);
  41.     vector<int> dist(n, INF);
  42.    
  43.     dist[S] = 0;
  44.    
  45.     priority_queue<node> pq;
  46.     pq.push(node(S, 0));
  47.    
  48.     while(!pq.empty()) {
  49.         node current_node = pq.top();
  50.         pq.pop();
  51.        
  52.         if(visited[current_node.idx]) {
  53.             continue;
  54.         }
  55.         visited[current_node.idx] = true;
  56.        
  57.         for(int i = 0; i < (int) graph[current_node.idx].size(); i++) {
  58.             int neighbour = graph[current_node.idx][i].first;
  59.             int weight = graph[current_node.idx][i].second;
  60.            
  61.             if(!visited[neighbour] and current_node.shortest_path + weight < dist[neighbour]) {
  62.                 dist[neighbour] = current_node.shortest_path + weight;
  63.                 pq.push(node(neighbour, dist[neighbour]));
  64.             }
  65.            
  66.         }
  67.     }
  68.    
  69.     cout << dist[E] << endl;
  70.    
  71.    
  72.    
  73.    
  74.     return 0;
  75. }
  76.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement