알고리즘

  • 일반적인 다익스트라로 푸는데, 풀면서 이전에 어디서 왔는지를 기록한다.
  • 다익스트라가 끝나고, 끝에서부터 왔던길을 되돌아가며 경로를 찾아낸다.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#define INF 2000000000000
 
typedef long long ll;
using namespace std;
 
int n, m, s, e, path[1001];
vector<int> p;
vector<pair<int, int>> to[1001];
priority_queue<pair<ll, int>> q;
ll cost[1001];
 
void dijkstra();
void checkPath();
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		to[a].push_back({ b, c });
	}
	cin >> s >> e;
 
	dijkstra();
	checkPath();
	cout << cost[e] << "\n";
	cout << p.size() << "\n";
	for (int i = p.size()-1; i >= 0; i--)
		cout << p[i] << " ";
}
 
void dijkstra() {
	for (int i = 0; i <= n; i++)
		cost[i] = INF;
 
	cost[s] = 0;
	path[s] = -1;
	q.push({ 0, s });
	while (!q.empty()) {
		ll c = -q.top().first;
		int cur = q.top().second;
		q.pop();
 
		if (c > cost[cur])
			continue;
 
		for (int i = 0; i < to[cur].size(); i++) {
			ll nc = c + to[cur][i].second;
			int ncur = to[cur][i].first;
 
			if (nc < cost[ncur]) {
				cost[ncur] = nc;
				path[ncur] = cur;
				q.push({ -nc, ncur });
			}
		}
	}
	return;
}
 
void checkPath() {
	int cur = e;
	while (path[cur] != -1) {
		p.push_back(cur);
		cur = path[cur];
	}
	p.push_back(cur);
}