BOJ 1948 - 임계 경로

www.acmicpc.net/problem/1948

1948번: 임계경로

 

---

위상정렬을  이용한 문제인데..

문제 자체 이해가 어렵다.

최단거리가 아닌, 최장 거리를 구하고.. 그때 간선의 개수를 구하는 문제이다.

DP 스럽게 풀었다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOJ1948 {
    static int N, M;
    static int S, E, cnt;
    static int[] D;
    static ArrayList<Node>[] VT;
    static boolean[] visit;
    static class Node {
        int e, v;
        Node(int e, int v){
            this.e = e;
            this.v = v;
        }
    }
    static void dfs(int cur){
        if(visit[cur]) return;
        visit[cur] = true;

        for (Node n: VT[cur]) {
            if(D[cur] == D[n.e] + n.v) {
                cnt++;
                dfs(n.e);
            }
        }
    }
    static void max_len(int cur) {
        for (Node n: VT[cur]) {
            if(D[n.e]==0) max_len(n.e);
            D[cur] = Math.max(D[cur], D[n.e] + n.v);
        }
    }
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/input_boj_1948.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long Start = System.currentTimeMillis();
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        VT = new ArrayList[N+1];
        D = new int[N+1];
        visit = new boolean[N+1];
        cnt = 0;

        for (int i = 1; i <= N ; i++) {
            VT[i] = new ArrayList<>();
        }

        int a, b, c;
        for (int i = 1; i <= M ; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            VT[a].add(new Node(b, c));
        }

        st = new StringTokenizer(br.readLine());
        S = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        max_len(S);
        dfs(S);

        System.out.println(D[S]);
        System.out.println(cnt);
    }
}