問題
1번 ~ N번까지 N개의 도시가 있고, 지호는 1번 도시에 살고 있다.
각 도시를 잇는 양방향 도로가 M개 있고, 각 도로를 통과하는데 걸리는 시간도 주어져 있다.
지호는 도로를 통과하지 않고, 텔레포트를 할 수 있다.
A 번 도시에서 B 번 도시로 텔레포트를 하면, ( A - B )를 제곱한 만큼 의 시간이 걸린다.
예를 들어, 3번 도시에서 7번 도시로 텔레포트를 하는 데에는 ( 3 - 7 )2 = 16 의 시간이 걸린다.
텔레포트는 무한히 할 수 없고, 최대 P 번까지만 가능하다.
이 상황에서, 지호가 살고 있는 1번 도시로부터,
각 도시까지 가는 데 걸리는 최단 시간을 모두 구해보자.
輸入
첫 줄에 세 정수 N, M, P 가 주어진다. ( 2 ≤ N ≤ 10만, 1 ≤ M ≤ 10만, 0 ≤ P ≤ 20 )
그 후 M 줄에 걸쳐 세 정수 S, E, T 가 입력된다. ( 1 ≤ S, E ≤ N, S ≠ E, 1 ≤ T ≤ 10억 )
S 번 도시와 E 번 도시를 잇는 양방향 도로를 통과할 때 T 의 시간이 걸린다는 뜻이다.
중복 간선이 있을 수 있다.
지호는 텔레포트 능력자이기 때문에, 주어진 그래프가 꼭 연결 그래프일 필요는 없다.
( 단, P = 0 일 때는 텔레포트가 불가능하므로, 무조건 연결 그래프로 입력 되는 것이 보장된다. )
輸出
1 ≤ i ≤ N 에 대해, 1번 도시에서 i 번 도시로 갈 수 잇는 최단 시간을 출력한다.
( 즉, N 개의 정수들을 출력한다. )
子任務
| 編號 | 分數 | 條件 |
|---|---|---|
| #1 | 20分 | 주어진 그래프는 연결 그래프이며, P = 0 이다. |
| #2 | 30分 | P = 1 , 1 ≤ N ≤ 1,000 |
| #3 | 30分 | P = 1 |
| #4 | 20分 | 제약 조건 없음 |
範例 #1
6 5 0
1 5 77
3 6 2
6 2 35
3 4 98
4 1 3
0 138 101 3 77 103
P = 0 이다. 텔레포트 없이 입력된 도로만 사용한다.
範例 #2
6 5 1
1 5 77
3 6 2
6 2 35
3 4 98
4 1 3
0 1 4 3 4 6
P = 1, 즉 한 번까지 텔레포트를 할 수 있다.
1번 : 비용 0 이다. (제자리)
2번 : 1 → 2 텔레포트
3번 : 1 → 4 도로, 4 → 3 텔레포트
4번 : 1 → 4 도로
5번 : 1 → 4 도로, 4 → 5 텔레포트
6번 : 1 → 4 도로, 4 → 3 텔레포트, 3 → 6 도로
需要登入才能撰寫程式碼。