https://www.acmicpc.net/problem/1948
1948번: 임계경로
첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의
www.acmicpc.net
1. 모두가 만나는 시간
"도착점에 가장 늦게 도착했을 때, 걸리는 경로의 시간"
2. 1분도 쉬지 않고 달려야 하는 도로
"도착점에 가장 늦게 도착하는 경로"를 의미
그대로 대입해보면, "도착점에 가장 늦게 도착하는 경로로 움직일 때, 지나는 도로의 수"
1번은 '게임 개발'과 똑같다. 단지 시작점이 결정되어 있을 뿐.
2번은 역방향 그래프를 이용해서 도시의 개수를 증가해나간다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> graph;
vector<vector<pair<int, int>>> r_graph;
vector<int> indegree; // 진입 차수
graph.resize(n + 1);
r_graph.resize(n + 1);
indegree.resize(n + 1);
for (int i = 0; i < m; i++)
{
int s, e, v;
cin >> s >> e >> v;
graph[s].push_back(make_pair(e, v));
r_graph[e].push_back(make_pair(s, v));
indegree[e]++;
}
int start, end;
cin >> start >> end;
queue<int> q;
q.push(start);
vector<int> result;
result.resize(n + 1);
// 위상정렬
while (!q.empty())
{
int now = q.front();
q.pop();
for (pair<int, int> next : graph[now])
{
indegree[next.first]--;
result[next.first] = max(result[next.first], result[now] + next.second);
if (indegree[next.first] == 0)
q.push(next.first);
}
}
// 위상정렬 reverse
int cnt = 0;
vector<bool> visited;
visited.resize(n + 1);
queue<int> rq;
rq.push(end);
visited[end] = true;
while (!rq.empty())
{
int now = rq.front();
rq.pop();
for (pair<int, int> next : r_graph[now])
{
//1분도 쉬지 않는 도시 체크
if (result[next.first] + next.second == result[now])
{
cnt++;
// 중복 방지 위해 방문 노드 제외
if (visited[next.first] == false)
{
visited[next.first] = true;
rq.push(next.first);
}
}
}
}
cout << result[end] << '\n';
cout << cnt << '\n';
return 0;
}
|
cs |