백준 9370번 미확인 도착지 C++ 다익스트라, 최단 경로

리뷰

예상 도착지가 주어 졌을때 출발 노드에서 도착 노드까지의 경로 중 일부 경로가 포함 되어있는지를 확인 해야하는 문제

 

문제 풀이

1. 테스트 케이스를 통해 구분된다, 각 테스트 케이스를 반복문을 통해 열어준다.
2. 노드 수 n, 간선의 수 m, 예상 도착지의 수 t, 시작 노드 s, 포함 간선을 나타내기 위한 g, h를 받아온다.
3. 간선을 양방향으로 받아 주고, 예상 도착지 t개를 입력 받고 오름차순으로 정렬해 준다.
4. 다시 t개의 예상 도착지를 순회하며 출발지 부터 예상 도착지 까지의 최단 거리를 구해준다.
5. g와 h를 포함하여 도착지 까지 가는 거리를 찾고, 둘을 비교하여 같다면 도착 노드를 출력해 준다.

 

참고 사항

g와 h를 포함하여 도착지 까지 가는 거리를 찾는 방법은 s -> g -> h -> 도착노드 이거나 s -> h -> g -> 도착 노드이다.

어떤 경로에서는 s -> g로 갈때 해당 경로에 h가 이미 존재할 수도 있고, 아닐 수도 있으니 두 케이스를 모두 구한 뒤 작은 값을 선택해 주었다, C++ 치곤 시간이 꽤 걸린 것 같다. 최적화 방법이 더 있을지도?

 

정답 코드

#include<iostream>
#include<vector>
#include<climits>
#include<queue>
#include<algorithm>

using namespace std;

int tc, n, m, t, s, g, h;

struct Pos {
	int d, node;
	bool operator<(const Pos& other) const {
		return d > other.d;
	}
};

int dijkstra(vector<vector<Pos>>& lst, int sn, int en) {
	priority_queue<Pos> pq;
	pq.push({ 0, sn });
	vector<int> dist(n + 1, INT_MAX);
	dist[sn] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cd = pos.d, cn = pos.node;
		if (dist[cn] != cd) continue;

		for (Pos cur : lst[cn]) {
			int nd = cur.d, nn = cur.node;
			if (dist[nn] > cd + nd) {
				dist[nn] = cd + nd;
				pq.push({ dist[nn], nn });
			}
		}
	}
	return dist[en];
}

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

	cin >> tc;
	for (int c = 1; c <= tc; c++) {
		cin >> n >> m >> t >> s >> g >> h;
		vector<vector<Pos>> lst(n + 1);
		for (int i = 0; i < m; i++) {
			int a, b, d;
			cin >> a >> b >> d;
			lst[a].push_back({ d, b });
			lst[b].push_back({ d, a });
		}
		vector<int> dn(t);
		for (int i = 0; i < t; i++) cin >> dn[i];
		sort(dn.begin(), dn.end());

		for (int i = 0; i < t; i++) {
			int md = dijkstra(lst, s, dn[i]);
			int wd = min(dijkstra(lst, s, g) + dijkstra(lst, g, h) + dijkstra(lst, h, dn[i]), dijkstra(lst, s, h) + dijkstra(lst, h, g) + dijkstra(lst, g, dn[i]));
			if (md == wd) cout << dn[i] << " ";
		}
		cout << "\n";
	}
}