Last active
June 4, 2020 10:25
-
-
Save oha-yashi/97277a1e424134f2288f63c8e841ad6e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment