Gidhub BE Developer

# BOJ - 최단경로

2018-04-04
goodGid

## Problem

Problem URL : 최단경로

## [1] Answer Code (18. 04. 04)

``````
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#define INF 987654321
#define p pair<int,int>
using namespace std;

vector<p> vc[20001];
int trace[20001];

int main(){
memset(trace, -1, sizeof(trace));
int v,e;
cin >> v >> e;

int st;
cin >> st;

for(int i=0; i<e; i++){
int from, to, val;
scanf("%d%d%d",&from,&to,&val);
vc[from].push_back(p(to,val));
}

int dist[20001];
fill(dist, dist + 20001, INF);
dist[st] = 0;

priority_queue<p, vector<p>, greater<p>> pq;
pq.push({ 0,st });

while (! pq.empty()) {
int here = pq.top().second;
int hereCost = pq.top().first;
pq.pop();

if(dist[here] < hereCost)
continue;

for(int i=0; i<vc[here].size(); i++){
int next = vc[here][i].first;
int nextCost = vc[here][i].second + hereCost;

if( dist[next] > nextCost){
dist[next] = nextCost;
trace[next] = here;
pq.push({ nextCost,next  });
}
}
}

for(int i=1; i<=v; i++){
if( dist[i] == INF)
printf("INF\n");
else
printf("%d\n",dist[i]);
}

return 0;
}

``````