[백준 1948번] 임계경로

문제 링크: https://www.acmicpc.net/problem/1948

1948번: 임계경로

<문제 풀이> 그래프 탐색, 위상 정렬

 

도착 도시에 가장 마지막에 도착하는 시간은 해당 도시로 들어오는 모든 출발 도시들이 도착한 시점입니다. 이를 모든 도시에 대해 순차적으로 고려하면 DAG이기 때문에 위상 정렬로 답을 구할 수 있습니다.

도로를 지나는 횟수를 계산하기 위해 역방향 간선을 추가로 입력 받아 도착 도시에서 BFS를 수행합니다. 만약 u에서 v로 이동하는데 필요한 시간이 cost라고 한다면, (u에 마지막으로 도착하는 시간 - cost == v에 마지막으로 도착하는 시간)이라면, 해당 간선은 위상 정렬에서 사용되었기 때문에 카운트해 주면 됩니다.

 

<C++소스코드>

 

#include<iostream>
#include<vector>
#include<utility>
#include<queue>
#include<cstring>
using namespace std;

const int MAX_N = 10000;

int n, m;
vector<pair<int, int> >adj[MAX_N + 1];
vector<pair<int, int> >rev_adj[MAX_N + 1];
bool visited[MAX_N + 1];
int indegree[MAX_N + 1];
int dist[MAX_N + 1];
int st, en;

int TopologicalSort() {
    queue<int> Q;
    Q.push(st);
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (auto& nxt : adj[cur]) {
            int nxt_dist = nxt.first + dist[cur];
            int nxt_idx = nxt.second;
            if (dist[nxt_idx] < nxt_dist) {
                dist[nxt_idx] = nxt_dist;
            }
            indegree[nxt_idx]--;
            if (indegree[nxt_idx] == 0) {
                Q.push(nxt_idx);
            }
        }
    }
    return dist[en];
}

int FindPath() {
    queue<int> Q;
    Q.push(en);
    int ret = 0;
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (auto& nxt : rev_adj[cur]) {
            int cost = nxt.first;
            int nxt_idx = nxt.second;
            if (dist[cur] - cost == dist[nxt_idx]) {
                ret++;
                if (!visited[nxt_idx]) {
                    visited[nxt_idx] = true;
                    Q.push(nxt_idx);
                }
            }
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({ w, v });
        indegree[v]++;
        rev_adj[v].push_back({ w, u });
    }

    cin >> st >> en;
    cout << TopologicalSort() << '\n';
    cout << FindPath();
    return 0;
}