[백준] 1948. 임계경로

https://www.acmicpc.net/problem/1948

1948번: 임계경로

 

## 접근법

출발지점에서 도착지점까지 오래 걸리는 시간과 해당 경로의 개수를 구해야 한다. 

 

출발지점에서 도착지점까지 오래 걸리는 시간을 구하기 위해 나는 아래와 같은 일차원 배열을 선언했다.

dist[노드번호] = 노드번호까지 가는데 걸리는 최대시간

그리고 경로를 추적해야하기 때문에 일차원 벡터 배열을 선언했다.

vector<int> prv[노드번호] = 노드번호로 in-degree한 노드번호들의 벡터

 

전략은 다음과 같다.

1) bfs로 모든 경로를 탐색한다.

2) 노드(a)로 in-degree하는 상황을 가정한다.

  - 만약 dist[a]보다 오래 걸리는 경로라면 dist[a]를 해당시간으로 초기화한다. 그리고 a로 들어오는 노드를 prv[a]에 추가한다.

  - 만약 dist[a]만큼 걸린다면, a로 들어오는 노드를 prv[a]에 추가한다

  - 만약 dist[a]보다 짧게 걸린다면 in-degree하지 않는다. 

3) dfs로 도착 노드로 들어왔던 경로를 탐색하여 경로의 개수를 구한다.

 

코드로 보기

```cpp

#include <bits/stdc++.h>
using namespace std;
#define init cin.tie(0)->sync_with_stdio(0)
#define ii pair<int, int>

int n, m;
int dist[10005];
vector<ii> adj[10005];
vector<int> prv[10005];
bool visited[10005];


int st, en;
void bfs() {
  queue<ii> q;
  q.push({st, 0});

  while(q.size()) {
    auto [cur, distance] = q.front();
    q.pop();

    for(auto [nxt, cost]: adj[cur]) {

      if(dist[nxt] < distance + cost) {
        dist[nxt] = distance + cost;
        prv[nxt].clear();
        prv[nxt].push_back(cur);
        q.push({nxt, distance + cost});
      }
      else if(dist[nxt] == distance + cost) {
        prv[nxt].push_back(cur);
      }

    }
  }
}
int cnt;
bool firstwhere = false;

void dfs(int cur) {
  if(visited[cur]) return;
  if(cur == st) return; 

  visited[cur] = true;
  cnt += prv[cur].size();

  for(auto x: prv[cur]) {
    dfs(x);
  }
}

int main() {
  init;
  cin >> n >> m;
  for(int i=0; i<m; i++){
    int a, b, c;
    cin >> a >> b >> c;
    adj[a].push_back({b, c});
  }
  cin >> st >> en;
  bfs();
  dfs(en);
  // for(auto x: prv[6]) { cout << x << ' '; }

  cout << dist[en] << '\n';
  cout << cnt;
}

```