[백준] 11779 최소 비용 구하기 2 + 복습

문제

n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.

입력

첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

둘째 줄에는 그러한 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력한다. 출발 도시와 도착 도시도 포함한다.

셋째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력한다.

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
vector<pi>adj[1001];
int dist[1001], ret[1001], ans[1001];
vector<int>answer;
int sz;
void print(int k) {
	if (k == 0)return;
	print(ans[k]);
	answer.push_back(k);
}
int dij(int from, int to) {
	priority_queue<pi,vector<pi>,greater<pi>>pq;
	memset(dist, 0x3f, sizeof(dist));
	pq.push({ 0,from });
	dist[from] = 0;	
	while (!pq.empty()) {
		auto [cdist, cur] = pq.top(); pq.pop();
		if (cur == to)break;
		for (auto [nxt,cost] : adj[cur]) {
			if (dist[nxt] > cdist + cost) {
				ans[nxt]=(cur);
				dist[nxt] = cdist + cost;
				pq.push({ dist[nxt],nxt });
			}
		}
	}
	return dist[to];
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m, a, b, c, from, to;
	cin >> n >> m;
	while (m--) {
		cin >> a >> b >> c;
		adj[a].push_back({ b,c });
	}
	cin >> from >> to;
	cout << dij(from, to) << "\n";
	print(to); 
	cout<< answer.size() << "\n";
	for (auto r : answer) {
		cout << r << " ";
	}
}

최소 비용 구하기 1 과 다른점은, 최소 비용을 갖는 경로에 포함되어있는 도시의 개수뿐만 아니라 출발 도시와 도착 도시도 포함한다. 그리고 셋째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력한다.

 

한 정점에서 다른 정점으로 이동하는데 비용이 모두 다르므로, 다익스트라 알고리즘을 사용해야합니다.

최단 거리는 다익스트라 알고리즘으로 쉽게 구할 수 있지만, 방문하는 도시를 구하는게 중요합니다.

 

다익스트라 알고리즘의 각 단계에서는 현재 방문할 수 있는 가장 가까운 도시를 기준으로 다른 모든 도시들을 갱신합니다.

따라서, 현재 도시를 cur 이라고 할때, i 번 도시를 갱신한다고 하면 ret[i]=cur로 저장합니다.

이때 이 ret[i]는 이후에 갱신될지 안될지 알 수 없습니다. 언젠가 i번째 도시는 cur이 될것이고, 그때 그 도시로 향하는 최단거리는 확정이 됩니다.

예를 들어보겠습니다. a.b,c,d,e......도시가 있습니다.

a,b,c도시가 현재도시 cur로 갱신한 여력이 있으며 현재 d도시가 현재도시 cur인 상황에서는

현재 d 도시를 마지막으로 갱신한 도시는 a,b,c 중 존재합니다. 즉, 확정되어있습니다.  d도시를 마지막으로 갱신한 도시가 c라고 하면, c도시도 마찬가지로 a,b 중 c도시를 마지막으로 갱신한 도시가 존재하고 확정되어있습니다.

a>>b>>c>>d 순으로 방문합니다.

 

만약에 d도시를 c도시가 갱신하기 전에 b도시가 갱신한 경우에는 어떻게 될까?

b도시는 d도시도 갱신했지만 ,c도시도 갱신했습니다.

이때 갱신된 d의 거리보다, c의 도시가 더 짧으므로 c도시가 cur이 됩니다. 따라서 결국 d도시는 c에의해 다시 갱신됩니다. 

 

따라서 ret[d] : c, ret[c] :b, ret[b]: a가 저장이 되면 a>b>c>d순으로 도시를 방문하게 됩니다. 

따라서 이 재귀를 이용한 알고리즘은 타당합니다.

 

============================================================================================복습..........

 

 

다익스트라 알고리즘을 사용하면서 

위 코드를 그대로 사용하면 이미 방문한 노드에 대해서 또다시 방문을 해버리면 어떻게 하지?

분명히 그럴 수 있습니다

그리고 실제로 pq.front()에 의해 이미 들어와 갱신했던 노드가 또다시 들어올 수 있습니다.

 

하지만 그 노드가 다시 들어왔다는 뜻은 처음 방문했을때 dist값이 더 작기때문에

그 노드와 연결된 dist[n]>cdist+cost 를 만족하지 못하기 때문에 다른 노드들이 또다시 갱신될 일이 없습니다.

따라서 그냥 나가게 됩니다.

 

영 불안하면 visited 방문처리를 해주어도 됩니다.

아래와 같습니다.

 

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int>pi;
int N, M ,dist[1001];
vector<pi>adj[1001];
int parent[1001], cnt, v[1001];
vector<int>ans;
void print(int to) {
	if (to == 0)return;
	print(parent[to]);
	ans.push_back(to);
}
int dij(int from, int to) {
	memset(dist, 0x3f, sizeof(dist));
	dist[from] = 0;
	priority_queue<pi, vector<pi>, greater<pi>>pq;
	pq.push({ 0,from });
	while(!pq.empty()){
		auto [d, cur] = pq.top(); pq.pop();
		v[cur] = 1;
		if (cur == to)break;
		for (auto [nxt, cost] : adj[cur]) {
			if (!v[nxt] && dist[nxt] > d + cost) { //미 방문노드에 대해
				dist[nxt] = d + cost;
				parent[nxt] = cur;
				pq.push({ dist[nxt],nxt });
			}
		}
	}
	return dist[to];
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	int a, b, c;
	while (M--) {
		cin >> a >> b >> c;
		adj[a].push_back({ b,c });
	}
	int from, to;
	cin >> from >> to;
	cout << dij(from, to) << "\n";
	print(to);
	cout << ans.size() << "\n";
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << " ";
	}
}