Advertisement
Josif_tepe

Untitled

Mar 20th, 2024
362
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.55 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <list>
  5. #include <queue>
  6. #include <cstring>
  7. #define ll long long
  8. #define ps push_back
  9. using namespace std;
  10. struct node{
  11.     int idx;
  12.     ll shortest_path;
  13.    
  14.     node(int i,ll s){
  15.         idx = i;
  16.         shortest_path = s;
  17.     }
  18.     bool operator < (const node &tmp) const {
  19.         return shortest_path > tmp.shortest_path;
  20.     }
  21. };
  22. vector<pair<int,int>> graph[100050];
  23. int main() {
  24.     int n,m;
  25.     cin >>n >> m;
  26.    
  27.     for(int i = 0;i<m;i++){
  28.         ll a,b,c;
  29.         cin >> a >> b>> c;
  30.         graph[a].push_back(make_pair(b, c));
  31. //        graph[b].push_back(make_pair(a, c));
  32.     }
  33.    
  34.  
  35.         priority_queue<node> pq;
  36.         vector<ll> dist(n+1,1e18);
  37.         vector<bool> visited(n+1,false);
  38.         dist[1] = 0;
  39.         pq.push(node(1,0));
  40.    
  41.         while(!pq.empty()){
  42.             node curr = pq.top();
  43.             pq.pop();
  44.            
  45.             if(visited[curr.idx]) continue;
  46.             visited[curr.idx] = true;
  47.             for(int j = 0;j<graph[curr.idx].size();j++){
  48.                 int sosed = graph[curr.idx][j].first;
  49.                 ll pat =  graph[curr.idx][j].second;
  50.                
  51.                 if(!visited[sosed] and curr.shortest_path+pat < dist[sosed]){
  52.                     pq.push(node(sosed,curr.shortest_path+pat));
  53.                     dist[sosed] = curr.shortest_path+pat;
  54.                    
  55.                 }
  56.             }
  57.         }
  58.     for(int i = 1;i<= n;i++){
  59.         cout << dist[i] << " " ;
  60.     }
  61. }
  62.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement