060 : 세일즈맨의 고민

(Briefing)
(문제)	(단 하나의 맥락)	(입출력과 되어야 하는 그림)
N개의 도시 (0~'N-1') 교통수단과 비용 도시 방문시마다 수익 도착 도시에 왔을 때, 돈의 총량 최대	"벨만-포드" + Money배열	I // 도시 수 N, S도시, E도시, 교통수단수 M (1) 교통 수단 : 시작 끝 가격 ... (M) : 시작 끝 가격 (1)도시의 수익 ~ (N)도시 수익 O // 최댓값 출력 도착할 수 없음 : gg 무한히 많이 지닐 때 : Gee

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    // Argument recognition
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M, sCity, eCity;
    static long D[], cMoney[];
    static Edge edges[];

    public static void main(String[] args) throws IOException {

        // Input Supply Cable
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        sCity = Integer.parseInt(st.nextToken());
        eCity = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());


        // Preprocessing
        edges = new Edge[M];
        D = new long[N];
        cMoney = new long[N];
        Arrays.fill(D, Long.MIN_VALUE);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(start, end, price);
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cMoney[i] = Long.parseLong(st.nextToken());
        }


        // Operating Bellman-ford
        D[sCity] = cMoney[sCity];
        for (int i = 0; i <= N+100; i++) {
            for (int j = 0; j < M; j++) {
                int start = edges[j].start;
                int end = edges[j].end;
                int price = edges[j].price;

                if (D[start] == Long.MIN_VALUE)
                    continue;
                else if (D[start] == Long.MAX_VALUE)
                    D[end] = Long.MAX_VALUE;
                else if (D[end] < D[start] + cMoney[end] - price) {
                    D[end] = D[start] + cMoney[end] - price;
                    if (i >= N-1) D[end] = Long.MAX_VALUE;
                }
            }
        }
        
        // Output Extracting Cable
        if (D[eCity] == Long.MIN_VALUE)
            System.out.println("gg");
        else if (D[eCity] == Long.MAX_VALUE)
            System.out.println("Gee");
        else 
            System.out.println(D[eCity]);
    }
}

// External class
class Edge {
    int start, end, price;
    public Edge(int start, int end, int price) {
        this.start = start;
        this.end = end;
        this.price = price;
    }
}