글 읽기 - 이 문제에서 왜 다익스트라가 안되나요? 혹시 관련 반례를 주실 수 있으신가요?

lucian0910 4년 전 0

저는 처음에 다익스트라로 풀었는데 최장거리는 적용이 안된다는 얘기를 듣고 dp로 선회해서 풀긴 했습니다. 그런데 왜 최장거리는 다익스트라가 안되는지 적절한 반례가 생각이 나지 않네요... 혹시 직관적인 반례를 주실 수 있으신가요? 아래는 제가 맨 처음에 다익스트라 써서 풀려고 했던 코드입니다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = -987654321;
typedef pair<int, int> P;

int build_time[1000];

void dijkstra() {

}

int main() {
	int T;
	scanf("%d", &T);

	for (int t = 0; t < T; t++) {
		int N, K, W;//N: 건물개수, K: 규칙 수, W: 목표 건물
		vector<int> inv[1000];

		scanf("%d %d", &N, &K);

		for (int i = 0; i < N; i++)
			scanf("%d", &build_time[i]);

		for (int i = 0; i < K; i++) {
			int s, e;

			scanf("%d %d", &s, &e);
			inv[e - 1].push_back(s - 1);
		}

		scanf("%d", &W);

		int dist[1000];
		fill(dist, dist + N, INF);
		bool visited[1000] = { 0, };
		priority_queue<P, vector<P>> PQ;

		dist[W - 1] = build_time[W - 1];
		PQ.push(P(build_time[W - 1], W - 1));
		while (!PQ.empty()) {
			int curr;
			do {
				curr = PQ.top().second;
				PQ.pop();
			} while (!PQ.empty() && visited[curr]); // curr가 방문한 정점이면 무시
			// 더 이상 방문할 수 있는 정점이 없으면 종료
			if (visited[curr]) break;

			visited[curr] = true; // 방문
			for (int next : inv[curr]) {
				int d = build_time[next];
				// 거리가 갱신될 경우 PQ에 새로 넣음
				if (dist[next] < dist[curr] + d) {
					dist[next] = dist[curr] + d;
					PQ.push(P(dist[next], next));
				}
			}
		}

		int result = 0;
		for (int i = 0; i < N; i++) {
			result = max(result, dist[i]);
		}
		printf("%d\n", result);
	}
}

djm03178 4년 전 0

다음 예시를 생각해 보세요.

1
6 6
1 1 2 2 1 0
1 2
2 3
2 4
3 6
4 5
5 6
6

정답: 5
출력: 4

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 문제에서 왜 다익스트라가 안되나요? 혹시 관련 반례를 주실 수 있으신가요?

lucian0910 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말