https://www.acmicpc.net/problem/14554
요약
정점 S에서 출발하여 E에 도달하는 서로 다른 최단경로의 개수를 구한다.
1. 정점 S에서 E로 가는 최단경로는 다익스트라를 통해 구할 수 있다.
2. 서로 다른 최단경로의 개수를 구하기 위해서는 다익스트라로 최단거리를 찾는 과정에서 정확히 어떤 경로로 이동하였는지를 기록하여야 한다.
https://int-p.tistory.com/13
3. 최단경로의 개수는 도착 정점부터 시작하여 시작 정점으로 거슬러 올라가면서 각 정점에 도달할 수 있는 경우의 수를 모두 더한 것과 같다.
간단한 그래프에서 이를 확인해볼 수 있다.
4. 기록한 경로와 DP를 통해 중복되는 정점의 값을 저장하며 답을 도출할 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, int> pli;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1000000009;
struct cmp {
bool operator() (pli A, pli B) {
return A.first > B.first;
}
};
int N, M, S, E;
vector <pli> graph[100001];
long long dist[100001];
vector <int> path[100001];
long long table[100001];
void Dijkstra(int start);
long long Find_PathNum(int vertex);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M >> S >> E;
for (int i = 0; i < M; i++) {
int A, B;
long long C;
cin >> A >> B >> C;
graph[A].push_back({ C,B });
graph[B].push_back({ C,A });
}
Dijkstra(S);
table[S] = 1;
cout << Find_PathNum(E);
return 0;
}
void Dijkstra(int start) {
for (int i = 1; i <= N; i++) dist[i] = INF;
priority_queue <pli, vector<pli>, cmp> pq;
pq.push({ 0, start });
dist[start] = 0;
while (pq.size()) {
int now = pq.top().second;
long long val = pq.top().first;
pq.pop();
if (dist[now] < val) continue;
for (int i = 0; i < graph[now].size(); i++) {
int next = graph[now][i].second;
long long new_val = val + graph[now][i].first;
if (dist[next] > new_val) {
dist[next] = new_val;
path[next].clear();
path[next].push_back(now);
pq.push({ new_val, next });
}
else if (dist[next] == new_val) path[next].push_back(now);
}
}
}
long long Find_PathNum(int vertex) {
if (table[vertex] != 0) return table[vertex];
for (int i = 0; i < path[vertex].size(); i++) table[vertex] = (table[vertex] + Find_PathNum(path[vertex][i])) % mod;
return table[vertex];
}
원글: https://int-p.tistory.com/14
'풀이 포스팅 > 3팀(목요일 20:00 ~)' 카테고리의 다른 글
[백준 5719번] 거의 최단 경로 / Almost Shortest Path, C++ 풀이 (0) | 2022.11.25 |
---|---|
[백준 11779번] 최소비용 구하기 2, C++ 풀이 (0) | 2022.11.24 |
[백준 14611번] 월요병, C++ 풀이 (0) | 2022.11.24 |
[백준 17833번] 홍익대학교 지하캠퍼스, C++ 풀이 (1) | 2022.11.24 |
[백준 20046번] Road Reconstruction, C++ 풀이 (0) | 2022.11.24 |