백준 14554번, The Other Way

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

14554번: The Other Way

 

요약

 

정점 S에서 출발하여 E에 도달하는 서로 다른 최단경로의 개수를 구한다.

---

1. 정점 S에서 E로 가는 최단경로는 다익스트라를 통해 구할 수 있다.

 

2. 서로 다른 최단경로의 개수를 구하기 위해서는 다익스트라로 최단거리를 찾는 과정에서 정확히 어떤 경로로 이동하였는지를 기록하여야 한다. 
https://int-p.tistory.com/13

다익스트라(Dijkstra) 알고리즘과 최단경로 역추적

 

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];
}