문제
민승이는 놀러가기 위해 집을 나섰다. 민승이네 집에서 코레스코 콘도까지 가기 위해서는 복잡하게 얽혀있는 골목길들을 통과해야 한다.
그런데, 어떤 길에는 깡패가 서식하고 있어, 그 길을 지나게 되면 깡패에게 일정한 양의 금품을 갈취당하게 된다. 그런가하면, 어떤 길에는 지나가던 행인들이 흘리고 간 금품들이 떨어져 있어, 그 길을 지나게 되면 일정한 양의 금품을 획득하게 된다. 한 번 지나간 길을 다시 방문하더라도 금품을 갈취당하거나 획득한다.
골목길의 연결 상태와, 각 골목길을 지날 때 갈취당하거나 획득하게 되는 금품의 양이 주어졌을 때, 민승이가 최대한 유리한 경로를 따라 집에서 코레스코 콘도까지 가기 위해서는 어떻게 해야 하는지 출력하는 프로그램을 작성하시오.
보유 중인 금품의 양이 음수가 될 수 있다. 최대한 유리한 경로 또는 최적의 경로는 민승이네 집에서 출발하여 코레스코 콘도에 도착하는 경로 중 금품의 양이 최대가 되는 경로이다.
입력
첫째 줄에 골목길들이 교차하는 지점의 개수 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풀이
이 문제는 벨만-포드 알고리즘을 이용해서 풀 수 있었다. 기본적으로 벨만-포드 알고리즘을 이용하고 이 문제에서는 최댓값을 구하기 때문에 최소 코스트 대신 최대 코스트를 구했다. 또한 원래는 음수 싸이클 찾지만 이 문제를 풀기 위해서 양수 싸이클을 찾는 방법으로 변형했다. 여기에서 중요한 점은 세 가지를 고려해야 한다. 우선, 도착지점을 갈 수 없는 경우 -1을 출력하고 사이클이 있는 경우 사이클이 도착지점을 지나갈 때도 -1을 출력해야 한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static Pair[] edge;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int n = Integer.parseInt(input[0]);
int m = Integer.parseInt(input[1]);
edge = new Pair[m];
int[] len = new int[n+1];
for(int i=1; i<=n; i++) {
len[i] = Integer.MIN_VALUE;
}
for(int i=0; i<m; i++) {
input = br.readLine().split(" ");
edge[i] = new Pair(Integer.parseInt(input[0]), Integer.parseInt(input[1]), Integer.parseInt(input[2]));
}
len[1] = 0;
int[] path = new int[n+1];
for(int i=0; i<n-1; i++) {
for(int j=0; j<m; j++) {
if(len[edge[j].start]==Integer.MIN_VALUE) continue;
if(len[edge[j].end] < len[edge[j].start]+edge[j].cost) {
len[edge[j].end] = len[edge[j].start] + edge[j].cost;
path[edge[j].end] = edge[j].start;
}
}
}
ArrayList<Integer> list = new ArrayList<>();
for(int j=0; j<m; j++) {
if(len[edge[j].start]==Integer.MIN_VALUE) continue;
if(len[edge[j].end] < len[edge[j].start]+edge[j].cost) {
list.add(edge[j].end);
}
}
if(len[n]==Integer.MIN_VALUE) {
System.out.println(-1);
return;
}
if(list.size()!=0) {
boolean[] v = bfs(list, n);
if(v[n])
System.out.println(-1);
else {
StringBuilder sb = new StringBuilder();
int j = n;
sb.append(n);
while(path[j]!=0) {
sb.insert(0, path[j]+" ");
j = path[j];
}
System.out.println(sb.toString());
}
}
else {
StringBuilder sb = new StringBuilder();
int j = n;
sb.append(n);
while(path[j]!=0) {
sb.insert(0, path[j]+" ");
j = path[j];
}
System.out.println(sb.toString());
}
}
public static boolean[] bfs(ArrayList<Integer> list, int N) {
boolean[] visited = new boolean[N+1];
for(int j=0; j<list.size(); j++) {
int start = list.get(j);
if(!visited[start]) {
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.add(start);
while(!queue.isEmpty()) {
int temp = queue.poll();
for(int i=0; i<edge.length; i++) {
Pair next = edge[i];
if(temp==next.start && !visited[next.end]) {
visited[next.end] = true;
queue.add(next.end);
}
}
}
}
}
return visited;
}
public static class Pair {
int start;
int end;
int cost;
public Pair(int start, int end, int cost) {
this.start = start;
this.end = end;
this.cost = cost;
}
}
}