[백준 1948] 임계경로 (C++)

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

1948번: 임계경로

1. 주의할 점

- 위상정렬 혹은 다익스트라로 풀 수있는 문제지만 나는 다익스트라로 해결했다.

- 우선, 다익스트라를 지금까지 완전히 잘못 사용하고 있었다.

if (dist[cidx] > cv) continue;
/*if (visit[cidx]) continue;
visit[cidx] = true;*/

주석처럼 사용할 경우 최장경로를 제대로 갱신할 수 없다. 짧은 길이 여러개로 이뤄져서 한참으로 돌아오고 있는 총 누적거리가 긴 경로는 짧은 길로 이미 해당 Node를 방문해서 다음 경로를 진행하고 있다면 최장거리는 갱신되지 않는다.

쉽게 설명하기 위해 밑의 그림을 첨부한다(빨간 숫자: 가중치, 파란 숫자: Node)

- 경로를 기억하는 과정이 여러가지 존재하지만 상당히 까다롭다.

 

2. 구현

- 입력을 받을 때, 정방향과 더불어 역방향의 그래프를 저장한다(역방향의 경우 도착지점 -> 시작지점을 알아내기 위해)

- 다익스트라를 통해서 시작지점 -> 도착지점까지의 최장거리를 구한다. + Dist배열에 시작지점 -> 다른 모든 Node까지의 거리를 구해놓는다.

- 도착지점을 -> 시작지점을 통해 경로를 구한다. 구하는 방법은 다음과 같다.

  도착지점에서 이동할 수 있는 Node로 간선의 가중치 만큼 이동했을 때, 이동한 Node의 Dist[Node] +가중치 = Dist[도착지점] 이면 Result++하고, 해당 Node에 처음 방문했다면 Queue에 저장해서 시작지점에 도착할 때까지 이어나간다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
	int idx, val, cnt;
};
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val < b.val;
	}
};
info tmp;
vector<info> v[10001];		//정방향 도로
vector<info> rev[10001];	//역방향 도로
long long dist[10001];
bool visit[10001] = { false, };

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int node, edge, s, e, val, result = 0, start, target;
	cin >> node >> edge;
	for (int i = 0; i < edge; i++) {
		cin >> s >> e >> val;
		tmp.idx = e;
		tmp.val = val;
		v[s].push_back(tmp);
		tmp.idx = s;
		rev[e].push_back(tmp);
	}
	for (int i = 1; i <= node; i++)
		dist[i] = -1;
	cin >> start >> target;
	priority_queue<info,vector<info>,cmp> pq;
	tmp.idx = start;
	tmp.val = 0;
	dist[start] = 0;
	pq.push(tmp);
	//최장거리 다익스트라
	while (!pq.empty()) {
		int cidx = pq.top().idx;
		int cv = pq.top().val;
		pq.pop();
		if (dist[cidx] > cv) continue;
		/*if (visit[cidx]) continue;
		visit[cidx] = true;*/
		for (int i = 0; i < v[cidx].size(); i++) {
			int next = v[cidx][i].idx;
			int nv = v[cidx][i].val;
			if (dist[next] < cv + nv) {
				dist[next] = cv + nv;
				tmp.idx = next;
				tmp.val = cv + nv;
				pq.push(tmp);
			}
		}
	}
	//역방향도로 시작
	for (int i = 1; i <= node; i++) {
		cout << dist[i] << " ";
		visit[i] = false;
	}
	system("pause");
	queue<int> q;
	q.push(target);
	visit[target] = true;
	while (!q.empty()) {
		int cidx = q.front();
		q.pop();	
		for (int i = 0; i < rev[cidx].size(); i++) {
			int next = rev[cidx][i].idx;
			int nv = rev[cidx][i].val;
			if (dist[next] + nv == dist[cidx]) {
				result++;
				if (!visit[next]) {
					q.push(next);
					visit[next] = true;
				}
			}
		}
	}
	cout << dist[target] << '\n' << result;
	system("pause");
	return 0;
}