Gidhub BE Developer

# BOJ - 최소비용 구하기2

2018-04-04
goodGid

## Problem

Problem URL : 최소비용 구하기2

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

``````

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

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

int main(){
int n, m;
cin >> n >> m;

memset(trace, -1, sizeof(trace));
for(int i=0; i<m; i++){
int from, to, val;
scanf("%d%d%d",&from,&to,&val);
vc[from].push_back(p(to,val));
}

int st,end;
cin >> st >> end;

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

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

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

// [3]
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  });
}
}
}

cout << dist[end] << endl;
int cnt = 1;
stack<int> s;

// [2]
for(int i=end; i != st; i = trace[i]){
cnt++;
s.push(i);
}
cout << cnt << endl;

s.push(st);
while (! s.empty()) {
printf("%d ",s.top());
s.pop();
}
return 0;
}

``````

## Code Review

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

• [1], [2] : Dijkstra 기본 구조

• 오랜만에 풀어보는 Dijkstra 문제 어려웠다.
하지만 너무 재밌었다.

• [3] : 생략하고 제출해도 맞았다. 하지만 효율성을 위해서 생략하지 말자 !