골목길

https://www.acmicpc.net/problem/1738

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	5531	932	552	17.824%

문제

민승이는 놀러가기 위해 집을 나섰다.

민승이네 집에서 코레스코 콘도까지 가기 위해서는 복잡하게 얽혀있는 골목길들을 통과해야 한다.

그런데, 어떤 길에는 깡패가 서식하고 있어, 그 길을 지나게 되면 깡패에게 일정한 양의 금품을 갈취당하게 된다.

그런가하면, 어떤 길에는 지나가던 행인들이 흘리고 간 금품들이 떨어져 있어, 그 길을 지나게 되면 일정한 양의 금품을 획득하게 된다. 

한 번 지나간 길을 다시 방문하더라도 금품을 갈취당하거나 획득한다.

골목길의 연결 상태와, 각 골목길을 지날 때 갈취당하거나 획득하게 되는 금품의 양이 주어졌을 때,

민승이가 최대한 유리한 경로를 따라 집에서 코레스코 콘도까지 가기 위해서는 어떻게 해야 하는지 출력하는 프로그램을 작성하시오. 

보유 중인 금품의 양이 음수가 될 수 있다. 

최대한 유리한 경로 또는 최적의 경로는 민승이네 집에서 출발하여 코레스코 콘도에 도착하는 경로 중 금품의 양이 최대가 되는 경로이다. 

입력

첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과

골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다.

이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 주어진다.

이는 u번 교차점에서 v번 교차점으로 이동할 수 있는 골목길이 나있다는 의미이다.

즉, 주어지는 골목길들은 기본적으로 모두 일방통행로이다.

w (0 ≤ |w| ≤ 1,000)는 이 길을 지날 때 갈취당하거나 획득하게 되는 금품의 양이다.

음수는 갈취, 양수는 획득을 뜻한다.

골목길의 교차점 번호는 1이상 n이하의 정수이다.

민승이네 집은 1번 교차점에 있고, 이곳 코레스코 콘도는 n번 교차점에 있다.

출력

최적의 경로를 구할 수 있다면 민승이네 집부터 코레스코 콘도까지 가는 동안 거치게 되는

교차점들의 번호를 공백 하나를 사이에 두고 차례로 출력하면 된다. 

그런데, 경우에 따라서는 최적의 경로라는 것이 존재하지 않는 상황이 발생한다.

어떠한 경우에 그런 상황이 발생하는지 생각해 보자. 

그러한 경우에는 -1을 출력하도록 한다.

최적의 경로가 여러 개 존재할 때는 아무거나 출력해도 된다.

예제 입력 1

5 7
1 2 3
1 3 4
3 1 -7
2 3 2
3 4 1
4 2 -5
4 5 1

예제 출력 1

1 2 3 4 5

예제 입력 2

5 7
1 2 3
1 3 4
3 1 -7
2 3 2
3 4 1
4 2 -2
4 5 1

예제 출력 2

-1

출처

• 문제를 번역한 사람: author10
• 빠진 조건을 찾은 사람: kcm1700

알고리즘 분류

• 그래프 이론
• 벨만–포드

---

알고리즘 – 벨만-포드 (Bellman–Ford Algorithm) 알고리즘 정리

---

주의 사항

이 문제는 Bellman–Ford 알고리즘을 사용할 때 사이클이 있다고 해서 무조건 -1 을 출력하면 안된다.

해당 사이클이 최적의 경로에 영향이 있는지 확인이 필요하다.

통과된 코드

#include <iostream>
#include <vector>

using namespace std;

constexpr long long int INF = INT64_MAX;

constexpr int MAXN = 101;

vector<pair<int, int>> graph[MAXN];

long long int disArr[MAXN];

// N : 지점의 개수, M : 골목길의 개수
int N, M, u, v, w;

int trace[MAXN];

int main()
{

	ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
	// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
	cin.tie(NULL);
	std::cout.tie(NULL);

	cin >> N >> M;

	fill(disArr, disArr + MAXN, INF);

	disArr[1] = 0;

	for (int i = 0; i < M; i++) {
		cin >> u >> v >> w;
		// 단방향
		graph[u].push_back(make_pair(v, -w));
	}


	// (모든 정점의 수 - 1) 번 확인한다.
	// N 번은 순환 체크
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 0; j < graph[i].size(); j++) {

				int u = i; // 시작점
				int v = graph[i][j].first; // 도착점
				int weight = graph[i][j].second; // 가중치

				// 만약 임시 배열이 무한대가 아니고 &&
				// 시작 임시 배열의 가중치가 도착지의 가중치보다 크다면
				if (disArr[u] != INF && disArr[u] + weight < disArr[v]) {
					disArr[v] = disArr[u] + weight;
					trace[v] = u;

					// K == N 일때 새로 업데이트 된다는 의미는 
					// 사이클에 포함되거나 사이클에서 도착 지점으로 도달 가능
					// 다음의 disArr[N] == -INF 코드를 통하여 영향이 있는 경로인지 판별 
					if (k == N) disArr[v] = -INF;
					// -INF로 더이상 업데이트를 막는다.
				}
			}
		}
	}

	if (disArr[N] == INF || disArr[N] == -INF) cout << "-1";
	else {
		// 경로를 역으로 추적한다.
		int now = N;
		vector<int> myV;
		while (now != 0) {
			myV.push_back(now);
			now = trace[now]; 
		}

		for (auto it = myV.rbegin(); it != myV.rend(); ++it) cout << *it << " ";

	}

	return 0;
}

추가 반례

예제 입력 A

4 4
1 2 1
2 3 1
3 2 1
1 4 1

예제 출력 A

1 4

예제 입력 B

7 11
1 2 3
1 3 4
3 1 -7
2 3 2
3 4 1
4 2 -5
4 7 1
4 5 1
5 6 2
6 5 3
6 7 -1000

예제 출력 B

-1

예제 입력 C

5 7
1 2 1
2 3 1
3 4 1
4 5 1
1 5 10
1 2 50
2 5 80

예제 출력 C

1 2 5

예제 입력 D

5 5
1 2 -1
2 3 1
3 4 1
4 2 1
2 5 -1

예제 출력 D

-1

예제 입력 E

4 4
1 4 3
2 3 1
3 2 1
4 2 1

예제 출력 E

1 4

예제 입력 F

4 5
1 2 1
2 3 1
3 4 1
3 2 1
4 1 1

예제 출력 F

-1

예제 입력 G

4 5
1 2 1
2 3 1
3 4 1
3 1 1
4 1 1

예제 출력 G

-1

예제 입력 H

5 5
1 2 1
2 3 1
3 4 1
4 3 1
2 5 1

예제 출력 H

1 2 5