백준 BOJ 1948 임계경로

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

1948번: 임계경로

문제 해설

월드 나라는 모든 도로가 일방통행인 도로이고, 사이클이 없다.

출발 도시는 들어오는 도로가 0개이고, 도착 도시는 나가는 도로가 0개이다.

수많은 사람들이 각각 모든 도로를 지나가며 여행을 할 때, 가장 늦게 오는 경로(들)를 구하는 문제다.

 

일방통행이고 사이클이 없으므로 어떤 경로로 가는지에 상관없이 갈 수 있는 만큼 쭉~ 가다보면 도착 도시에 도착하게 된다.

 

해야 할 일은 다음과 같다.

1. 출발 도시를 큐에 넣는다.

2. 큐에서 도시(now) 하나를 빼고, 그 도시에서 갈 수 있는 다른 도시들(next)을 바라본다.

3. next들 중, now로 부터 왔을 때,

3-1. 소요되는 시간이 현재 소요되는 시간과 같다면 next에서 바라본 이전 도시(prev)에 now를 추가한다.

3-2. 소요되는 시간이 현재 소요되는 시간보다 크다면, next에서 바라본 이전 도시(prev)를 모두 비우고, now를 넣는다.

4. 현재 도시(now)에서 갈 수 있는 도시(next)가 없을 때까지 2부터 3 과정을 계속한다.

 

소프트웨어 공학에서 배운 임계 경로(Critical Path)와 같으므로 개념을 구현만 하면 된다.

본인은 get_no_rest(쉬지 않고 달려야 하는 도로의 수를 구하는 함수)를 구현하다 시간 초과가 났다.

다른 분의 풀이는 본인처럼 visited을 무식하도록 여유롭게 주지 않고, vector로 타이트하게 가져갔다.

 

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)

using namespace std;

#include <set>
#include <queue>
#include <vector>

vector<pair<int, int> > can_go_from[10001];//갈 수 있는 노드, 거리
vector<int> prev_node[10001];//가장 늦은 루트 중 이전 노드
int residue[10001];//남아있는 들어오는 도로의 수
int cost[10001]; // 해당 지역을 지나는 가장 늦은 시간

bool visited[10001][10001];
int no_rest;
void get_no_rest(int now, int start_node){
	if(now != start_node){
		for(int i=0; i<prev_node[now].size(); i++){
			if(visited[now][prev_node[now][i]]) continue;
			no_rest++;
			visited[now][prev_node[now][i]] =true;
			get_no_rest(prev_node[now][i], start_node);
		}
	}
}

int main() {
	fio;
	int N, M; cin >> N >> M;
	for(int i=0; i<M; i++){
		int from, to, dist;
		cin >> from >> to >> dist;
		can_go_from[from].push_back(make_pair(to, dist));
		residue[to]++;
	}
	//
	int start_node, end_node; cin >> start_node >> end_node;
	queue<int> Q;
	Q.push(start_node);
	//
	while(!Q.empty()){
		int now_node = Q.front(); Q.pop();
		for(int i=0; i<can_go_from[now_node].size(); i++){
			int next_node = can_go_from[now_node][i].first;
			int time_cost = can_go_from[now_node][i].second;
			if(cost[next_node] < cost[now_node] + time_cost){
				cost[next_node] = cost[now_node] + time_cost;
				prev_node[next_node].clear();
				prev_node[next_node].push_back(now_node);
			}else if(cost[next_node] == cost[now_node] + time_cost){
				prev_node[next_node].push_back(now_node);
			}
			//
			residue[next_node]--;
			if(residue[next_node] == 0){
				Q.push(next_node);
			}
		}
	}
	//
	no_rest=0;
	get_no_rest(end_node, start_node);
	cout << cost[end_node]<<'\n';
	cout << no_rest;

	return 0;
}