1753 : 최단경로

풀이

다익스트라를 짜자

우선순위 큐를 쓰자

코드

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

const int v_ = 20000 + 1;
const int INF = 987654321;

struct edg {
	int idx, dst;
	edg() {}
	edg(int idx, int dst) : idx(idx), dst(dst) {}
	bool operator <(edg A)const { return dst > A.dst; }
};

int v, e, s, dst[v_];
vector<edg> gph[v_];

void dijkstra() {
	for (int i = 0; i < v; ++i) dst[i] = INF;
	dst[s] = 0;

	priority_queue<edg> pq;
	for (int i = 0; i < v; ++i) pq.push(edg(i, dst[i]));

	while (!pq.empty()) {
		edg now = pq.top(); pq.pop();

		if (now.dst != dst[now.idx]) continue;

		for (edg next : gph[now.idx]) {
			if (dst[next.idx] > now.dst + next.dst) {
				dst[next.idx] = now.dst + next.dst;
				pq.push(edg(next.idx, dst[next.idx]));
			}
		}
	}
}

int main() {
	scanf("%d %d", &v, &e);
	scanf("%d", &s); --s;

	for (int i = 0; i < e; ++i) {
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		--u, --v;
		gph[u].push_back(edg(v, w));
	}

	dijkstra();

	for (int i = 0; i < v; ++i) {
		dst[i] != INF ? printf("%d", dst[i]) : printf("INF");
		printf("\n");
	}

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-02-14 18:33

Read more posts by this author