Submission #54864624

Source Code Expand

import networkx as nx
import itertools

N, M = map(int, input().split())
G = nx.Graph()
G.add_nodes_from(range(1, N + 1))
G.add_weighted_edges_from([map(int, input().split()) for _ in range(M)])
S = nx.floyd_warshall(G)

ans = M
for i, j, d in G.edges(data=True):
    for s, t in itertools.combinations(G.nodes(), 2):
        if S[s][i] + d['weight'] + S[j][t] == S[s][t]:
            ans -= 1
            break
print(ans)

Submission Info

Submission Time
Task D - Candidates of No Shortest Paths
User H3PO4
Language Python (CPython 3.11.4)
Score 400
Code Size 439 Byte
Status AC
Exec Time 1259 ms
Memory 30436 KiB

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 104 ms 28600 KiB
sample_02.txt AC 104 ms 28508 KiB
subtask_1_01.txt AC 104 ms 28528 KiB
subtask_1_02.txt AC 121 ms 28848 KiB
subtask_1_03.txt AC 176 ms 29656 KiB
subtask_1_04.txt AC 183 ms 30052 KiB
subtask_1_05.txt AC 600 ms 30304 KiB
subtask_1_06.txt AC 112 ms 28728 KiB
subtask_1_07.txt AC 128 ms 29044 KiB
subtask_1_08.txt AC 196 ms 29964 KiB
subtask_1_09.txt AC 203 ms 29888 KiB
subtask_1_10.txt AC 209 ms 30024 KiB
subtask_1_11.txt AC 110 ms 28808 KiB
subtask_1_12.txt AC 135 ms 29076 KiB
subtask_1_13.txt AC 182 ms 29940 KiB
subtask_1_14.txt AC 301 ms 29936 KiB
subtask_1_15.txt AC 176 ms 29928 KiB
subtask_1_16.txt AC 105 ms 28536 KiB
subtask_1_17.txt AC 120 ms 28880 KiB
subtask_1_18.txt AC 176 ms 28872 KiB
subtask_1_19.txt AC 364 ms 29340 KiB
subtask_1_20.txt AC 123 ms 28920 KiB
subtask_1_21.txt AC 109 ms 28564 KiB
subtask_1_22.txt AC 133 ms 29356 KiB
subtask_1_23.txt AC 193 ms 28856 KiB
subtask_1_24.txt AC 777 ms 30328 KiB
subtask_1_25.txt AC 506 ms 29328 KiB
subtask_1_26.txt AC 416 ms 29404 KiB
subtask_1_27.txt AC 1116 ms 30436 KiB
subtask_1_28.txt AC 1259 ms 30124 KiB