백준
백준 1948 임계경로
콩순이냉장고
2021. 8. 4. 17:23
문제 URL : https://www.acmicpc.net/problem/1948
1948번: 임계경로
첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의
www.acmicpc.net
문제접근법 : 위상정렬을 이용해야한다는건 알고있었는데
꽤나 고생해서 풀었습니다. v1->v2로 가는경로가 하나로만 생각하면서 풀다 계속 왜틀리지 싶었는데'
v1->v2로 가는경로가 여러개로 생각을바꾸면 중복되는 경로를 제외 시키질 않아 여러번 틀렸네요
첫번째: start-> end까지 가는 위상정렬을 구하여 모든경로의 가장 최대값을 저장합니다. 그 저장한 배열을 cost 배열이라하겠습니다.
반대로 end-> start로 가는 경로로 가는데 cost[end]에서 하게되면 각경로를 역으로 지나올때
cost[end]-nextcost는 반드시 cost[cur]인 경로면 그경로는 맞는경로가됩니다.
그렇지만 중복을 피하기위해 visit을 꼭해줘야합니다.
소스코드 :
|
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
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int, int>> v[10001];
vector<pair<int, int>> v2[10001];
int indegree[10001];
vector<int> cost;
int start, finish;
int path = 0;
int check[10001];
void input() {
cin >> n;
cin >> m;
int a, b, c;
for (int i = 0; i < m; i++) {
cin >> a >> b >> c;
v[a].push_back({ b,c });
v2[b].push_back({ a,c });
indegree[b]++;
}
cin >> start >> finish;
}
void topology(int cur, int totalcost = 0) {
for (int i = 0; i < v[cur].size(); i++) {
int next = v[cur][i].first;
int ncost = totalcost + v[cur][i].second;
indegree[next]--;
cost[next] = max(cost[next], ncost);
if (indegree[next] == 0) {
topology(next, cost[next]);
}
}
}
void backtrack(int cur, int totalcost) {
if(check[cur])return;
check[cur]=1;
for (int i = 0; i < v2[cur].size(); i++) {
int next = v2[cur][i].first;
int ncost = totalcost - v2[cur][i].second;
if (cost[next] == ncost) {
path++;
backtrack(next, ncost);
}
}
}
void solve() {
cost.resize(n + 1);
topology(start);
cout << cost[finish] << "\n";
backtrack(finish, cost[finish]);
cout << path << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 논리적인 오류등 어떤질문이든 댓글은 언제나 환영입니다.