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
AC × 2
AC × 30
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