문제

문제 링크 : https://www.acmicpc.net/problem/1916

풀이

아주 간단한 다익스트라 문제이다.

문제에서 시키는 대로 입력을 받고 입력 받은 시작점을 기준으로 다익스트라를 한 번 돌린 뒤에 도착점까지의 거리 값을 출력하면 된다.

다익스트라 함수만 구현할 수 있으면 풀 수 있다.

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9 + 7;
int n, m, start, finish;
vector<pair<int,int>> graph[1001];
int dist[1001];

void dijkstra() {
	fill_n(dist, 1001, INF);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	dist[start] = 0;
	q.push({ 0,start });

	while (!q.empty()) {
		int d = q.top().first;
		int now = q.top().second;
		q.pop();

		if (d > dist[now]) continue;

		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].first;
			int next_d = d + graph[now][i].second;

			if (next_d < dist[next]) {
				dist[next] = next_d;
				q.push({next_d,next});
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	cin >> m;

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back({ b,c });
	}

	cin >> start >> finish;

	dijkstra();

	cout << dist[finish] << '\n';

	return 0;
}