백준 25953 (C++) 템포럴 그래프

최초 업로드: 2025-04-27 08:09:41

최근 수정 시간: 2025-07-25 09:01:38

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] 템포럴 그래프

[문제 링크](https://www.acmicpc.net/problem/25953)

## 문제 설명

템포럴 그래프는 시간의 흐름에 따라 변화하는 관계를 표현하는 자료 구조이다. 템포럴 그래프를 구성하는 정점 집합 $V$는 시간의 흐름에 따라 변하지 않으며, 정점의 개수가 $n ≥ 1$이라 할 때 $V$는 ${0, 1, dots , n - 1}$으로 나타낸다. 시간 표기 $T$는 양의 정수 $1, 2, dots , t$의 값을 가지며 시간 표기가 차례로 증가하는 것으로 시간의 흐름을 표현한다. 각 시간 표기 $T$에서 양의 정수인 가중치를 가지는 간선들의 집합 $E_T$가 정의되고, $E_T$에 포함되는 간선의 수는 일정하게 유지된다. 아래 그림은 정점 집합 $V = {0, 1, 2, 3, 4}$와 시간 표기 $T = 1, 2, 3, 4$에서 정의된 템포럴 그래프의 예시이다.

템포럴 그래프의 한 정점에서 다른 정점으로 향하는 경로는 증가하는 시간 표기에 따라 차례로 나타나는 간선들의 집합으로 구성된다. 경로를 구성할 때에는 각 시간 표기에서 최대 한 개의 간선을 선택할 수 있으며, 경로를 구성하는 간선들이 정의되는 시간 표기가 연속할 필요는 없다. 예를 들어, 위 그림의 템포럴 그래프에서 세 간선 $(0, 1)$, $(1, 2)$, $(2, 4)$를 각각 시간 표기 $T = 1, 2, 4$에서 선택한다면 이는 정점 $0$에서 정점 $4$로 향하는 경로가 된다. 하지만 세 간선 $(0, 2)$, $(2, 3)$, $(3, 4)$를 각각 시간 표기 $T = 1, 3, 2$에서 선택한다면 이는 정점 $0$에서 정점 $4$로 향하는 경로가 될 수 없다(왜냐하면, 선택된 시간 표기가 증가하지 않기 때문이다). 경로의 길이는 경로에 포함되는 간선의 가중치의 총 합으로 정의한다. 따라서, 두 간선 $(0, 2)$, $(2, 4)$를 각각 시간 표기 $T = 1, 4$에서 선택한다면 이는 정점 $0$에서 정점 $4$로 향하는 최단 길이 경로가 되고 경로의 길이는 $1 + 2 = 3$이 된다.

입력으로 템포럴 그래프와 경로의 시작과 끝이 되는 두 정점 $s$와 $e$가 주어질 때, $s$에서 $e$로 향하는 최단 길이 경로의 길이를 구하는 프로그램을 작성하시오.

## 입력

입력은 표준입력을 사용한다. 첫 번째 줄에 정점 집합의 크기를 나타내는 양의 정수 $n$ ($2 ≤ n ≤ 10,000$), 시간 표기의 범위를 나타내는 양의 정수 $t$ ($1 ≤ t ≤ 1,000$), 매 시간 표기마다 정의되는 간선들의 개수를 나타내는 양의 정수 $m$ ($1 ≤ m ≤ 1,000$)이 차례로 주어진다. 다음 줄에 경로의 시작이 되는 정점을 나타내는 정수 $s$와 경로의 끝이 되는 정점을 나타내는 정수 $e$ ($0 ≤ s ≠ e ≤ n - 1$)가 차례로 주어진다. 이어지는 $m$개의 줄은 시간 표기 $T = 1$에서 정의되는 간선들의 정보를 나타낸다. 특정한 두 정점을 연결하는 간선이 두 개 이상 나타나는 경우는 없다. 각 줄에는 간선이 연결하는 두 정점의 번호와 간선의 가중치를 나타내는 양의 정수 $w$ ($1 ≤ w ≤ 10,000$)가 차례로 주어진다. 이어지는 $m × (t − 1)$줄은 시간 표기 $T = 2, dots , t$에서 정의되는 간선들의 정보를 동일한 방식으로 나타낸다.

## 출력

출력은 표준출력을 사용한다. 정점 $s$에서 정점 $e$로 향하는 최단 길이 경로의 길이를 한 줄에 출력하고, 경로가 정의되지 않는 경우에는 $-1$을 출력한다.

## 풀이
#### dp[i][j]를 시간 i에서 s->j로의 최소 거리로 두고 풀었다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int dp[1001][10000]; // dp[i][j] : 시간 i일때 s -> j번 정점으로의 최소 거리

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, t, m, s, e; cin >> n >> t >> m >> s >> e;

for(int i=0;i<n;i++) dp[0][i]=INF;
 dp[0][s]=0;

for(int i=0;i<t;i++) {
 memcpy(dp[i+1], dp[i], sizeof dp[i]);
 for(int j=0;j<m;j++) {
 int u, v, w; cin >> u >> v >> w;
 dp[i+1][v] = min(dp[i+1][v], dp[i][u]+w);
 dp[i+1][u] = min(dp[i+1][u], dp[i][v]+w);
 }
 }
 cout << (dp[t][e]==INF ? -1 : dp[t][e]);
}
```