用户输出
1 2 3 3 2 3 4 4 5
系统信息
Exited with return code 0| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #5895 | #1061. 最短路问题 | Time Limit Exceeded | 40 | 19403 ms | 169300 K | Python 3 / 1.0 K | harkerbest | 2024-08-17 17:16:29 |
import heapq
def dijkstra(n, edges):
inf = float('inf')
dist = [inf] * (n + 1)
dist[1] = 0
pq = [(0, 1)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v in range(1, n + 1):
if u != v:
alt = d + abs(u - v)
if alt < dist[v]:
dist[v] = alt
heapq.heappush(pq, (alt, v))
for v, cost in edges[u]:
alt = d + cost
if alt < dist[v]:
dist[v] = alt
heapq.heappush(pq, (alt, v))
return dist
def solve(n, m, extra_edges):
edges = {i: [] for i in range(1, n + 1)}
for x, y, z in extra_edges:
edges[x].append((y, z))
edges[y].append((x, z))
dist = dijkstra(n, edges)
print(" ".join(map(str, dist[2:])))
n, m = map(int, input().split())
extra_edges = [tuple(map(int, input().split())) for _ in range(m)]
solve(n, m, extra_edges)
用户输出
1 2 3 3 2 3 4 4 5
系统信息
Exited with return code 0用户输出
1 2 3 4 5 5 4 5 5
系统信息
Exited with return code 0用户输出
1 2 3 2 3 4 3 4 5
系统信息
Exited with return code 0用户输出
1 2 3 4 5 5 6 5 6
系统信息
Exited with return code 01000 1000
386 311 62
947 590 264
442 765 286
781 232 263
342 830 357
254 490 144
787 531 157
856 254
<11270 bytes omitted>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 21 20 19 18 17 16 15 14 13 12 11 10 9 10 11 12
<2888 bytes omitted>用户输出
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 21 20 19 18 17 16 15 14 13 12 11 10 9 10 11 12 13 14 15 16 17 18 19 20 21
<2859 bytes omitted>系统信息
Exited with return code 01000 1000
488 851 248
98 734 233
785 205 551
545 950 234
999 300 205
341 592 88
440 152 108
157 840
<11248 bytes omitted>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 30 29 30 29 28 2
<2876 bytes omitted>用户输出
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 30 29 30 29 28 27 26 25 24 23 22 21 20 19 18
<2847 bytes omitted>系统信息
Exited with return code 01000 1000
183 188 4
320 628 957
199 480 161
31 78 47
328 607 99
458 436 743
367 158 180
309 802 365
<11245 bytes omitted>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3
<2886 bytes omitted>用户输出
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 37 36 35 34 33 32 31 30
<2857 bytes omitted>系统信息
Exited with return code 01000 1000
606 400 26
81 139 5
108 603 19
522 245 23
846 344 110
53 832 279
848 274 196
174 2 72
445
<11235 bytes omitted>1 2 3 4 5 6 7 8 9 10 11 12 11 10 9 8 7 6 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2
<2880 bytes omitted>用户输出
1 2 3 4 5 6 7 8 9 10 11 12 11 10 9 8 7 6 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 25 24 23 24 25 26 27 28 29
<2851 bytes omitted>系统信息
Exited with return code 0100000 30
66577 27574 15989
57497 64234 3847
70344 91131 2067
12766 80177 35761
73332 38638 20188
75
<419 bytes omitted>100000 30
476 59661 55988
76799 59777 6131
32697 88275 42059
34218 89384 5643
38185 67617 13787
6859
<432 bytes omitted>100000 30
2128 30547 18765
40047 80322 33301
82136 70025 7516
33768 66814 17118
37952 52558 12476
17
<431 bytes omitted>100000 30
77808 31672 35610
95082 46111 19236
44217 14265 1945
92386 1818 65252
65053 23506 9679
555
<422 bytes omitted>500000 500000
119637 206482 5305
415079 298250 7615
287208 350360 25447
82077 159253 21971
14650 475
<9909079 bytes omitted>500000 500000
32801 418343 23967
144010 479613 186699
411707 108288 49326
433635 393879 37266
371524
<9908808 bytes omitted>500000 500000
314249 208397 97409
189367 482804 231718
65738 427855 14488
131958 119538 455022
17299
<9907866 bytes omitted>