Shortest Routes I

1#include<bits/stdc++.h>
2using namespace std;
3#define int long long
4signed main(){
5  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
6  int n,m; cin>>n>>m;
7  vector<pair<int,int>> adj[n];
8  for(int i=0; i<m; ++i){
9    int a,b,c; cin>>a>>b>>c;
10    adj[--a].emplace_back(c,--b);
11  }
12  for(int i=0; i<n; ++i)
13    sort(adj[i].begin(),adj[i].end());
14  int dis[n]; memset(dis,0x3f,sizeof dis);
15  dis[0] = 0;
16  priority_queue<pair<int,int>>pq;
17  pq.emplace(0,0);
18  while(pq.size()){
19    pair<int,int> cur=pq.top(); pq.pop();
20    if(-cur.first>dis[cur.second]) continue;
21    for(auto&p:adj[cur.second]){
22      if(-cur.first+p.first>=dis[p.second]) continue;
23      dis[p.second]=p.first-cur.first;
24      pq.emplace(-dis[p.second],p.second);
25    }
26  }
27  for(int i=0; i<n; ++i)
28    cout<<dis[i]<<" ";
29  cout<<'\n';
30  return 0;
31}