Submission #50116550

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
//&は「参照渡し」調べてみよう
vector<long long>dijkstra(vector<vector<pair<int,long long>>>&g,int start){
  vector<long long>dist(g.size(),10000000000);
  dist[start]=0;
  priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>pq;
  pq.push({0,start});
  //pq.size()が1以上の間繰り返す
  while(pq.size()){
    //dには距離が、posには場所が入る（autoでpairを崩して（？）受け取るのすごい便利だよ！！）
    auto[d,pos] = pq.top();pq.pop();
    //dが最短距離じゃなかったらcontinue
    if(d>dist[pos])continue;
    //これも上と同じ、まとめて取り出す！
    for(auto[to,cost]:g[pos]){
      //最短距離を更新できなかったらcontinue
      if(dist[to]<dist[pos]+cost)continue;
      dist[to]=dist[pos]+cost;
      pq.push({dist[to],to});
    }
  }
  return dist;
}
int main(){
  int n,m;cin >> n >> m;
  //pairのfirstが行先、secondがコスト
  vector<vector<pair<int,long long>>>g(n);
  for(int i = 0;i<m;i++){
    int a,b,c;cin >> a >> b >> c;
    a--,b--;
    g[a].push_back({b,c});
    g[b].push_back({a,c});
  }
  vector<long long>ans = dijkstra(g,0);
  for(int i = 0;i<n;i++){
    if(ans[i]<10000000000)cout<< ans[i] <<endl;
    else cout << -1 << endl;
  }
}

Submission Info

Judge Result