글 읽기 - 연결 그래프라고 언급하거나 케이스를 추가해야 됩니다.

lucian0910 4년 전 7

처음에 문제를 잘못 이해해서 무조건 1번 도시를 출발점이라고 생각하고 아래와 같이 문제를 풀어서 성공이 떴습니다. 그런데 생각해보니 이 그래프가 연결 그래프라는 언급이 전혀 없으므로 컴포넌트가 여러개 이상일 수도 있는데, 그렇게 되면

5 1 3

1 2 3

3 4 1

4 5 1

5 3 1

위 케이스를 넣을 시 원래대로라면 3-4-5번 도시가 음수 사이클이므로 YES가 떠야 하는데 아래 코드에서는 1-2번 도시는 음수 사이클이 아니므로 NO가 뜹니다. 이 부분에 대해서 연결그래프라고 확실히 언급하거나 케이스를 추가해야 될 것으로 보입니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> P;

vector<P> adj[500];
int dist[500];

int main() {
	ios::sync_with_stdio(false);

	int T;
	const int INF = 25000001;//임의의 매우 큰 수

	cin >> T;
	for (int t = 0; t < T; t++) {
		int N, M, W;
		bool isReachable = false;
		cin >> N >> M >> W;

		//초기화
		for (int i = 0; i < N; i++) {
			adj[i].clear();
		}

		//도로 정보
		for (int i = 0; i < M; i++) {
			int s, e, t;
			cin >> s >> e >> t;
			adj[s - 1].push_back(P(e - 1, t));
			adj[e - 1].push_back(P(s - 1, t));
		}
		//웜홀 정보
		for (int i = 0; i < W; i++) {
			int s, e, t;
			cin >> s >> e >> t;
			adj[s - 1].push_back(P(e - 1, -t));
		}

		fill(dist, dist + N, INF);
		dist[0] = 0;//출발점이 무조건 첫번째 도시라 가정

		for (int i = 0; i < N; i++) {//벨만포드 알고리즘
			for (int j = 0; j < N; j++) {
				for (P nextP : adj[j]) {
					int next = nextP.first;
					int d = nextP.second;
					if (dist[j] != INF && dist[next] > dist[j] + d) {
						if (i == N - 1) {//음의 사이클 발견 시 성공
							isReachable = true;
						}
						dist[next] = dist[j] + d;
					}
				}
			}
		}

		if (isReachable)
			cout << "YES" << '\n';
		else
			cout << "NO" << '\n';
	}


	return 0;
}

jh05013 4년 전 0

간선에 방향이 있으므로 연결 그래프라고 하는 것은 의미가 없고, 데이터를 추가하는 것이 좋겠습니다.

동의합니다.

한 가지 특정 시작점에서만 벨만 포드 알고리즘을 적용하면 그 시작점에서 도달할 수 없는 경우를 고려하지 않은 소스도 맞은 것으로 나옵니다.

채점 테스트 케이스를 추가해야 합니다.

반례)
1
6 5 1
1 2 3
2 3 3
1 3 3
4 6 1
5 6 1
4 5 3

1번을 시작점으로 1회 벨만 포드 알고리즘 적용한 경우 : NO
모든 가능한 시작점을 고려한 경우 : YES

다만 이 경우 시작점에서 분리된 그래프의 음수 싸이클을 찾을 수 있는 장점이 있지만 시작점에서 최단거리를 찾을 수 있는 기능이 사라진다고 볼 수 있겠네요.

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

문제

문제

출처

ICPC

연결 그래프라고 언급하거나 케이스를 추가해야 됩니다.

lucian0910 4년 전 7

jh05013 4년 전 0

pf7 4년 전 0

manybirds 4년 전 0

bgoodsamari 4년 전 0

danbi2990 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말