/*
* 2025-07-25
* 문제060_백준 1219번
* */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static class Edge {
int to;
int weight;
Edge(int to, int weight){
this.to = to;
this.weight = weight;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int max[] = new int[N];
List<List<Edge>> graph = new ArrayList<>();
for(int i = 0; i <= N; i++){
graph.add(new ArrayList<>());
}
for(int i = 0; i < M; i++){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
graph.get(a).add(new Edge(b,c));
}
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++){
max[i] = Integer.parseInt(st.nextToken());
}
// 그러면 여기서 경로 + max 해서 다시 cost 값을 구한다음에 bellman ford 쓰면 될듯?
int dist[] = new int[N + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
// n-1번 돌면서 벨만 포드 조건 확인
for(int i = 1; i <= N-1; i++){
for(int j = 1; j <= N; j++){
for(Edge edge : graph.get(j)){
int to = edge.to;
int weight = edge.weight + max[i];
if(dist[j] != Integer.MAX_VALUE && dist[to] > dist[j] + weight){
dist[to] = dist[j] + weight;
}
}
}
}
boolean cycle = false;
// 마지막 n번째거는 음수를 확인한다.
for(int i = 1; i <= N; i++){
for(Edge edge : graph.get(i)){
int to = edge.to;
int weight = edge.weight;
if(dist[i] != Integer.MAX_VALUE && dist[to] > dist[i] + weight){
cycle=true;
break;
}
}
}
if(cycle){
System.out.println("gg");
}else{
// for(int i = 2; i<= N; i++){
// if(dist[i] == Integer.MAX_VALUE){
// System.out.println("-1");
// }else{
// System.out.println(dist[i]);
// }
// }
StringBuilder sb = new StringBuilder();
for (int i = 2; i <= N; i++) {
if (dist[i] == Integer.MAX_VALUE) {
sb.append("Gee\\n");
} else {
sb.append(dist[i]).append("\\n");
}
}
System.out.print(sb);
}
br.close();
}
}
흠 애초에 준 start와 end를 아예 사용 자체를 안하고 있으니 맞을리가 없긴 한데 논리적으로는 틀린 곳 없어보이는데..
문제점은 현재 단순 사이클이 있다는 것만으로 Gee를 출력하고 있다는 데에 있다
그 사이클이 start→end에서 도달이 가능한 경로에 있는지를 확인해야 한다.
→ dfs로 end까지 도달이 가능한지 확인해야 한다…..헐……..
Q) 그러면 앞에 문제에서는 단순 사이클이 있어서 -1 출력한 이유는?
앞 문제는 최단거리 문제니까 전체 사이클에서 하나라도 음수가 있으면 최단거리 의미가 없으니까 이 문제는 목적지까지 가는 경로 중 이득을 무한히 얻을 수 있는 경우만 문제인거니까
package day8.B1219;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static boolean[] visited; // for dfs
static boolean startToEnd = false;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int max[] = new int[N];
List<List<Edge>> graph = new ArrayList<>();
**for (int i = 0; i < N; i++) { // 여기는 또 왜 N+1까지 안해도 돌아가지?**
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
graph.get(a).add(new Edge(b, c));
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
max[i] = Integer.parseInt(st.nextToken());
}
long dist[] = new long[N];
Arrays.fill(dist, Long.MIN_VALUE);
dist[start] = max[start];
List<Integer> cycleNodes = new ArrayList<>();
// 벨만 포드 n-1번돌고
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < N; j++) {
if (dist[j] == Long.MIN_VALUE) {
continue;
}
for (Edge edge : graph.get(j)) {
int to = edge.to;
long weight = -edge.weight + max[to]; //여기가 그냥 + 가 아니라 - 임
if (dist[to] < dist[j] + weight) {
dist[to] = dist[j] + weight;
}
}
}
}
// N번째에서는 사이클 후보 저장
for (int j = 0; j < N; j++) {
if (dist[j] == Long.MIN_VALUE) {
continue;
}
for (Edge edge : graph.get(j)) {
int to = edge.to;
long weight = -edge.weight + max[to];
if (dist[to] < dist[j] + weight) {
cycleNodes.add(j); // 사이클의 후보가 되는거
}
}
}
// 사이클 후보 중에서 start->end 도당리 가능한거체크
visited = new boolean[N];
for (int node : cycleNodes) {
Arrays.fill(visited, false);
dfs(node, end, graph);
if (startToEnd) {
break;
}
}
if (startToEnd) {
System.out.println("Gee");
} else if (dist[end] == Long.MIN_VALUE) {
System.out.println("gg");
} else {
System.out.println(dist[end]);
}
br.close();
}
public static void dfs(int current, int end, List<List<Edge>> graph) {
if (current == end) {
startToEnd = true;
return;
}
visited[current] = true;
for (Edge edge : graph.get(current)) {
int next = edge.to;
if (!visited[next]) {
dfs(next, end, graph);
}
}
}
}
package day8.B1219;
public class Edge {
int to;
int weight;
Edge(int to, int weight){
this.to = to;
this.weight = weight;
}
}
이사람은 천재가 분명하다…조켓다