Programming/BOJ
[백준/BOJ] 1753 최단경로
he1fire
2020. 9. 26. 01:15
728x90
문제 : 1753 최단경로
1753번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다.
www.acmicpc.net
방향 그래프가 주어졌을 때, 시작점에서 다른 모든 점까지의
최단경로를 구해 출력하는 문제이다.
Dijkstra 알고리즘을 사용해 순회한 후 경로가 존재하는지
체크해 배열의 값을 출력하면 된다.
Code
#include <bits/stdc++.h>
#define ll long long
#define INF 987654321
using namespace std;
typedef pair<ll,ll> pll;
struct ABC
{
ll idx, dst;
ABC(){}
ABC(ll idx, ll dst): idx(idx), dst(dst) {}
};
bool operator<(ABC a, ABC b){
return a.dst>b.dst;
}
ll V, E, K, visit[20005];
vector<ABC> arr[20005];
priority_queue<ABC> pq;
void Dijkstra(){
fill(&visit[0], &visit[20004], INF);
pq.push(ABC(K,0));
visit[K]=0;
while (!pq.empty()){
ll curr=pq.top().dst, x=pq.top().idx;
pq.pop();
if (visit[x]<curr)
continue;
for (int i=0;i<arr[x].size();i++){
ll next=arr[x][i].dst, dx=arr[x][i].idx;
if (visit[dx]>curr+next){
visit[dx]=curr+next;
pq.push(ABC(dx,curr+next));
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> V >> E >> K;
for (int i=0;i<E;i++){
ll a, b, c;
cin >> a >> b >> c;
arr[a].push_back(ABC(b,c));
}
Dijkstra();
for (int i=1;i<=V;i++){
visit[i]==INF ? cout << "INF\n" : cout << visit[i] << "\n";
}
return 0;
}
728x90