https://o-treetree.hatenablog.com/entry/GRL1A

dijkstra_hatena.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 1LL<<60

using Edge = pair<ll, ll>; //辺
using Graph = vector<vector<Edge>>; //隣接リスト

ll V,E,r;
Graph G;
vector<ll> dist;

void dijkstra(){
  priority_queue<
    pair<ll, ll>,
    vector<pair<ll, ll>>,
    greater<pair<ll, ll>>
  >que;

  que.push({0, r});

  while(!que.empty()){

    auto now = que.top(); que.pop();
    ll nowDist = now.first;
    ll nowNode = now.second;

    if(nowDist > dist[nowNode])continue;

    for(Edge next: G[nowNode]){
      ll nextDir = next.first;
      ll nextWeight = next.second;

      if(dist[nextDir] <= dist[nowNode]+nextWeight)continue;
      dist[nextDir] = dist[nowNode] + nextWeight;
      que.push({dist[nextDir], nextDir});
    }
  }
}

int main(){
  cin>>V>>E>>r;
  G.resize(V);

  for(int i=0; i<E; i++){
    int s,t,d;
    cin>>s>>t>>d;
    G[s].push_back({t, d});
  }

  dist.resize(V, INF);
  dist[r] = 0;
  dijkstra();
  for(ll x: dist){
    if(x==INF){
      cout<<"INF"<<endl;
    }else{
      cout<<x<<endl;
    }
  }
}