Submission #2713688
Source Code Expand
from collections import deque N,M = map(int,input().split()) g = [[] for _ in range(0,N+1)] e = [] for i in range(0,M): a,b,t = map(int,input().split()) g[a].append((b,t)) g[b].append((a,t)) e.append((a,b,t)) d = [[float("inf") for _ in range(0,N+1)]for _ in range(0,N+1)] def dijkstra(s): d[s][s] = 0 queue = deque([[s,g[s]]]) while queue: start,edge = queue.popleft() for to,cost in edge: if d[s][to] > d[s][start] + cost: d[s][to] = d[s][start] + cost queue.append((to,g[to])) for i in range(1,N+1): dijkstra(i) ans = [1 for _ in range(0,M)] for i in range(1,N+1): j = 0 for a,b,t in e: if d[i][a] + t == d[i][b]: ans[j] = 0 j += 1 print(sum(ans))
Submission Info
Submission Time | |
---|---|
Task | D - Candidates of No Shortest Paths |
User | shinsakun |
Language | Python (3.4.3) |
Score | 400 |
Code Size | 812 Byte |
Status | AC |
Exec Time | 218 ms |
Memory | 4084 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt |
All | sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 21 ms | 3316 KB |
sample_02.txt | AC | 22 ms | 3316 KB |
subtask_1_01.txt | AC | 21 ms | 3316 KB |
subtask_1_02.txt | AC | 25 ms | 3444 KB |
subtask_1_03.txt | AC | 32 ms | 3816 KB |
subtask_1_04.txt | AC | 34 ms | 3948 KB |
subtask_1_05.txt | AC | 116 ms | 4080 KB |
subtask_1_06.txt | AC | 23 ms | 3444 KB |
subtask_1_07.txt | AC | 27 ms | 3572 KB |
subtask_1_08.txt | AC | 36 ms | 3948 KB |
subtask_1_09.txt | AC | 34 ms | 3952 KB |
subtask_1_10.txt | AC | 38 ms | 3952 KB |
subtask_1_11.txt | AC | 23 ms | 3444 KB |
subtask_1_12.txt | AC | 27 ms | 3572 KB |
subtask_1_13.txt | AC | 35 ms | 3952 KB |
subtask_1_14.txt | AC | 52 ms | 3952 KB |
subtask_1_15.txt | AC | 36 ms | 3952 KB |
subtask_1_16.txt | AC | 22 ms | 3316 KB |
subtask_1_17.txt | AC | 31 ms | 3444 KB |
subtask_1_18.txt | AC | 55 ms | 3444 KB |
subtask_1_19.txt | AC | 109 ms | 3572 KB |
subtask_1_20.txt | AC | 32 ms | 3444 KB |
subtask_1_21.txt | AC | 25 ms | 3316 KB |
subtask_1_22.txt | AC | 31 ms | 3572 KB |
subtask_1_23.txt | AC | 55 ms | 3444 KB |
subtask_1_24.txt | AC | 158 ms | 4076 KB |
subtask_1_25.txt | AC | 137 ms | 3700 KB |
subtask_1_26.txt | AC | 86 ms | 3828 KB |
subtask_1_27.txt | AC | 218 ms | 4084 KB |
subtask_1_28.txt | AC | 112 ms | 3956 KB |