32 lines
No EOL
679 B
Python
32 lines
No EOL
679 B
Python
import sys
|
|
|
|
input_data = sys.stdin.read().split()
|
|
N = int(input_data[0])
|
|
M = int(input_data[1])
|
|
K = int(input_data[2])
|
|
S = int(input_data[3]) - 1
|
|
edges = []
|
|
ptr = 4
|
|
for _ in range(M):
|
|
u = int(input_data[ptr]) - 1
|
|
v = int(input_data[ptr+1]) - 1
|
|
w = int(input_data[ptr+2])
|
|
edges.append((u, v, w))
|
|
ptr += 3
|
|
INF = 10**15
|
|
dp = [INF] * N
|
|
dp[S] = 0
|
|
for _ in range(K):
|
|
next_dp = [INF] * N
|
|
for u, v, w in edges:
|
|
if dp[u] != INF:
|
|
if dp[u] + w < next_dp[v]:
|
|
next_dp[v] = dp[u] + w
|
|
dp = next_dp
|
|
res = []
|
|
for val in dp:
|
|
if val == INF:
|
|
res.append("-1")
|
|
else:
|
|
res.append(str(val))
|
|
print("\n".join(res)) |