[백준] 1948 임계경로

시작점에서 끝점까지 가는데 가장 긴 경로를 출력하고 그때 지나가는 길의 수출력하는 문제다..!

가장 긴 경로 구하는건 쉬웠는데 지나온 길 찾는게 어려워따 ㅎㅎ

백준의 도움을 받아따 ㅎㅎ

문제는 위상정렬을 이용해서 풀었다!

위상정렬로 가장 긴 경로는 d[next] = max(d[next] , d[here]+cost)로 구할 수 있다

그리고 지나온 경로는 역으로 그래프를 만들어서 방문한 점중에 가장 긴 경로와 지나온 거리가 같다면 카운트를 올리는 식으로 했다!

DAG에서 가장 긴 경로 구하는 문제로 기억해둬야지 ㅎㅎ

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int n, m,d[10010],ind[10010],rind[10010],s,e,ans;
bool check[10010];
vector<vector<pair<int, int>>> Graph,rGraph;
 
int DIST(int x, int y) {
    queue <int> q;
    q.push(x);
    while (!q.empty()) {
        int here = q.front();
        q.pop();
        for (int i = 0; i < Graph[here].size(); i++) {
            int next = Graph[here][i].first;
            int ncost = Graph[here][i].second;
            d[next] = max(d[next], d[here] + ncost);
            ind[next]--;
            if (ind[next] == 0) q.push(next);
        }
    }
    return d[y];
}
 
void CNT(int x, int y) {
    queue<int> q;
    q.push(x);
    check[x] = true;
    while (!q.empty()) {
        int here = q.front();
        q.pop();
        for (int i = 0; i < rGraph[here].size(); i++) {
            int next = rGraph[here][i].first;
            int ncost = rGraph[here][i].second;
            if (check[here] && (d[here] - d[next] == ncost)) {
                check[next] = true;
                ans += 1;
            }
            rind[next]--;
            if (rind[next] == 0) q.push(next);
        }
    }
}
 
int main() {
    scanf(" %d %d", &n, &m);
    Graph.resize(n);
    rGraph.resize(n);
    for (int i = 0; i < m; i++) {
        int x, y, z; scanf(" %d %d %d", &x, &y, &z);
        x--; y--;
        Graph[x].push_back({ y,z });
        ind[y]++;
        rGraph[y].push_back({ x,z });
        rind[x]++;
    }
    scanf(" %d %d", &s, &e);
    s--; e--;
    int dist = DIST(s, e);
    CNT(e, s);
    printf("%d\n", dist);
    printf("%d\n", ans);
    return 0;
}