[BOJ 25953 // C++] 템포럴 그래프

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25953번 문제인 템포럴 그래프이다.
문제는 아래 링크를 확인하자.

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

25953번: 템포럴 그래프

시간 0에 노드 S에서 출발하여 시간 t에 노드 x까지 이동하는 최단경로는 시간 t-1에 이미 x에 도착해있었거나 t-1에 다른 노드에서 x로 이동해온 두 가지 경우중 하나로 찾을 수 있다.

 

위와 같은 관찰을 이용해 점화식을 세워 DP로 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, T, M, S, E;
int dist[1001][10000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> T >> M >> S >> E;
	for (int i = 0; i < N; i++) dist[0][i] = 1000000007;
	dist[0][S] = 0;
	for(int t = 0; t < T; t++) {
		for (int i = 0; i < N; i++) dist[t + 1][i] = dist[t][i];
		for (int i = 0; i < M; i++) {
			int x, y, w; cin >> x >> y >> w;
			dist[t + 1][y] = min(dist[t + 1][y], dist[t][x] + w);
			dist[t + 1][x] = min(dist[t + 1][x], dist[t][y] + w);
		}
	}

	if (dist[T][E] < 1000000007) cout << dist[T][E];
	else cout << -1;
}