[백준 1948] 임계경로 (C++)

1948번: 임계경로

 

단방향 그래프(DAG)임을 유의

 

특정 도시에서 모두 만나는데 걸리는 시간은 시작도시에서 특정 도시까지 가는데 걸리는 모든 시간 중 최댓값이 된다.

따라서 BFS를 통해 모든 정점에 대해 걸리는 시간 값을 구할 수 있다.

 

도착 정점까지 쉬지 않고 달려야 하는 사람이 지나는 도로의 개수의 의미는 도착 정점을 시작점으로 해서 되돌아 갈 때,  

'도착 정점까지 가는데 걸리는 시간 - 도착 정점을 시작으로 특정 정점까지 가는데 걸리는 시간 = 시작 정점에서 특정 정점까지 가는데 걸리는시간'

위 식을 만족한다면 해당 정점까지 가는데 통과한 도로가 답이 된다.

 

 

5 -> 6 = 2,   2 -> 7 = 5

time[1] = 0
time[2] = 4
time[3] = 2
time[4] = 3
time[5] = 3
time[6] = 7
time[7] = 12

 

7에서 6으로 가는데 5의 시간이 들고, 7까지 가는 시간에서 6까지 가는 시간을 빼면 5가 된다. 따라서 7-6 도로는 답에 해당하는 도로이다.

 

중요한 점은 방문한 정점을 체크해줘야 한다는 점이다. 체크해주지 않고 도로의 개수를 카운팅 하면 도로가 중복되어서 카운팅 될 수 있기 때문

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pii pair<int, int>
 
using namespace std;
 
int N, M, S, E, roadcnt;
vector<pii > graph[10001][2];
 
// 정점에 도달하는 시간
int time[10001];
 
void input(){
    cin >> N >> M;
    int u, v, c;
    for(int i = 0; i < M; i++){
        cin >> u >> v >> c;
        graph[u][0].push_back({v, c});
        graph[v][1].push_back({u, c});
    }
    cin >> S >> E;
}
 
void bfs(int k){
    queue<int> que;
    que.push(S);
    time[S] = 0;
    
    while(!que.empty()){
        int now = que.front();
        que.pop();
        
        for(int i = 0; i < graph[now][k].size(); i++){
            int next = graph[now][k][i].first;
            int next_time = graph[now][k][i].second + time[now];
            
            if(time[next] < next_time){
                time[next] = next_time;
                que.push(next);
            }
        }
    }
}
 
void rev_bfs(int k){
    queue<pii > que;
    que.push({E, 0});
    
    bool visited[10001];
    memset(visited, 0, sizeof(visited));
    visited[E] = true;
    
    while(!que.empty()){
        int now = que.front().first;
        int now_time = que.front().second;
        que.pop();
        
        for(int i = 0; i < graph[now][k].size(); i++){
            int next = graph[now][k][i].first;
            int next_time = graph[now][k][i].second + now_time;
            
            if(time[E] - next_time == time[next]){
                if(!visited[next]){
                    visited[next] = true;
                    roadcnt++;
                    que.push({next, next_time});
                }
                else roadcnt++;
            }
        }
    }
}
 
int main(){
    fastio
    input();
    bfs(0);
    rev_bfs(1);
    cout << time[E] << "\n" << roadcnt;
    
    return 0;
}