Advertisement
Josif_tepe

Untitled

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