문제 URL : https://www.acmicpc.net/problem/14554
14554번: The Other Way
첫째 줄에는 $N$, $M$, $S$, $E$가 하나의 공백으로 구분되어 들어온다. ($2 \le N \le 100000$, $N-1 \le M \le 300000$, $1 \le S, E \le N$, $S \neq E$) 그 후 $M$개의 줄에는 $A$, $B$, $C$가 하나의 공백으로 구분 되어 들어
www.acmicpc.net
문제 접근법 :
최단경로의 가짓수를 구하는 문제입니다. 간단하게 보면 한장소에서 원하는장소까지 최단거리를 구하는 문제면
다익스트라를 바로 생각할수 있지만 가짓수는 좀 고민을 하셔야할겁니다.
처음 다익스트라 + dfs를 이용하여 역추적하면서 구하다가 맞질않았는데
단순히 다익스트라 하나만으로도 경우의수를 구할수있습니다.
처음 경로의수를 구하니 해당간선들만을 찾고 그 간선들을 곱하기로 하는 실수를 범하기 쉬운데
예를들면
기존의 테스트 케이스에서 4번이란 노드를 하나더 만들고 4까지가는 최단거리는 3입니다.
즉 1번에서 4번으로 가게되기위해 3번을 거처지나가지만 3번을 가는 경로의수는 3이었죠 거기서 4의 간선은 2개이니
2를 곱하면 6이 되어 6이라고 곱하기의 규칙이 성립하는것 처럼보이지만 다르게
이와같은 간선을 추가하게된다면 1에서 4번으로 가는 최단거리의 경우의수는 8이 되버립니다. 즉 6+2가 되어 곱하기의 원리가 성립하질 않습니다.
그렇다면 어떻게 하면 좋을까요? 우선은 s에서 출발해서 e까지 가는경로의수는 반드시
하나이상은 존재한다고 봅시다 그럼 1에서 출발지점에서 우선 1개의 경로의수가 나옵니다. 그리고 최단거리를
구해보면
dist = [0,1,,2,3] 라는 결과값을 얻습니다. 여기서 인덱스는 1번부터 시작한다고 생각하시구
res=[1,0,0,0] 을봅니다. 우선 시작지점에서 경우의수를 1로생각하고 2번노드로 갔을때의경우의 수와 3번으로 갈때 경우의수는 1개이고 4로 갈때 경우의수 2개입니다.
res=[1,2,1,2]겠죠
그리고 다시 2번에서 3번으로 가는경우의수는 1개뿐이 지만 1번에서 2번으로 갈때의 경우스는 2개였으므로 2개 에서 1개를 그대로 더해줍니다.
[1,2,3,2] 가 되겠죠 그리고 3,에서 4로 가는경우의수는 3이지만
경로가 2개입니다. 즉 3을 2번더하면
[1,2,3,8] 즉 마지막 4번노드의 경우의수가 8개가 정확히 나옵니다.
소스코드 :
|
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
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P pair<ll,ll>
#define v vector
#define vl v<P>
#define vll v<vl>
ll n, m, s, e;
vll adj;
v<ll> dist, res;
ll mod = 1e9 + 9;
void input() {
cin >> n >> m >> s >> e;
adj = vll(n + 1);
ll a, b, c;
for (ll i = 0; i < m; i++) {
cin >> a >> b >> c;
adj[a].push_back({ b,c });
adj[b].push_back({ a,c });
}
}
void dijkstrak() {
dist = v<ll>(n + 1, 1e16);
priority_queue<P, v<P>, greater<P>> pq;
pq.push({ 0,s });
dist[s] = 0;
res = v<ll>(n + 1);
res[s] = 1;
while (!pq.empty()) {
ll cur, sumcost;
tie(sumcost,cur) = pq.top();
pq.pop();
if (dist[cur] < sumcost)continue;
for (ll i = 0; i < adj[cur].size(); i++) {
ll next = adj[cur][i].first;
ll ncost = sumcost + adj[cur][i].second;
if (dist[next] > ncost) {
dist[next] = ncost;
res[next] = res[cur];
pq.push({ ncost,next });
}
else if (dist[next] == ncost) {
res[next] += res[cur];
res[next] %= mod;
}
}
}
}
void solve() {
dijkstrak();
cout << res[e] << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 피보나치 수 6 (0) | 2022.10.20 |
|---|---|
| 백준 15730 수영장 사장님 (1) | 2022.08.04 |
| 백준 13911 집 구하기 (0) | 2022.07.31 |
| 백준 19237 어른 상어 (0) | 2022.07.21 |
| 백준 21611 마법사 상어와 블리자드 (0) | 2022.07.21 |
