Submission #6248667
Source Code Expand
import collections
import heapq
class Dijkstra():
def __init__(self):
self.e = collections.defaultdict(list)
def add(self, u, v, d, directed=False):
"""
#0-indexedでなくてもよいことに注意
#u = from, v = to, d = cost
#directed = Trueなら、有向グラフである
"""
if directed is False:
self.e[u].append([v, d])
self.e[v].append([u, d])
else:
self.e[u].append([v, d])
def delete(self, u, v):
self.e[u] = [_ for _ in self.e[u] if _[0] != v]
self.e[v] = [_ for _ in self.e[v] if _[0] != u]
def Dijkstra_search(self, s):
"""
#0-indexedでなくてもよいことに注意
#:param s: 始点
#:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev
"""
d = collections.defaultdict(lambda: float('inf'))
prev = collections.defaultdict(lambda: None)
d[s] = 0
q = []
heapq.heappush(q, (0, s))
v = collections.defaultdict(bool)
while len(q):
k, u = heapq.heappop(q)
if v[u]:
continue
v[u] = True
for uv, ud in self.e[u]:
if v[uv]:
continue
vd = k + ud
if d[uv] > vd:
d[uv] = vd
prev[uv] = u
heapq.heappush(q, (vd, uv))
return d, prev
def getDijkstraShortestPath(self, start, goal):
_, prev = self.Dijkstra_search(start)
shortestPath = []
node = goal
while node is not None:
shortestPath.append(node)
node = prev[node]
return shortestPath[::-1]
N, M = map(int, input().split())
graph = Dijkstra()
for i in range(M):
a, b, c = map(int, input().split())
graph.add(a-1, b-1, c, directed=False)
usedPaths = collections.defaultdict(set)
for i in range(N):
for j in range(i+1, N):
path = graph.getDijkstraShortestPath(i, j)
if len(path) == 2:
usedPaths[path[0]].add(path[1])
usedPaths[path[1]].add(path[0])
else:
for k, v in enumerate(path[:-1]):
usedPaths[v].add(path[k + 1])
usedPaths[path[k + 1]].add(v)
ans = M - sum([len(a) for a in list(usedPaths.values())])//2
print(ans)
Submission Info
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 |
163 ms |
38256 KB |
sample_02.txt |
AC |
163 ms |
38256 KB |
subtask_1_01.txt |
AC |
210 ms |
41964 KB |
subtask_1_02.txt |
AC |
372 ms |
54104 KB |
subtask_1_03.txt |
AC |
669 ms |
68188 KB |
subtask_1_04.txt |
AC |
457 ms |
51160 KB |
subtask_1_05.txt |
AC |
1390 ms |
86492 KB |
subtask_1_06.txt |
AC |
451 ms |
63452 KB |
subtask_1_07.txt |
AC |
349 ms |
51036 KB |
subtask_1_08.txt |
AC |
675 ms |
65216 KB |
subtask_1_09.txt |
AC |
518 ms |
55516 KB |
subtask_1_10.txt |
AC |
828 ms |
72920 KB |
subtask_1_11.txt |
AC |
329 ms |
52060 KB |
subtask_1_12.txt |
AC |
468 ms |
57692 KB |
subtask_1_13.txt |
AC |
674 ms |
63708 KB |
subtask_1_14.txt |
AC |
1076 ms |
85852 KB |
subtask_1_15.txt |
AC |
736 ms |
66780 KB |
subtask_1_16.txt |
AC |
234 ms |
44272 KB |
subtask_1_17.txt |
AC |
332 ms |
52700 KB |
subtask_1_18.txt |
AC |
501 ms |
62044 KB |
subtask_1_19.txt |
AC |
640 ms |
68060 KB |
subtask_1_20.txt |
AC |
372 ms |
55516 KB |
subtask_1_21.txt |
AC |
302 ms |
51036 KB |
subtask_1_22.txt |
AC |
621 ms |
68444 KB |
subtask_1_23.txt |
AC |
510 ms |
62940 KB |
subtask_1_24.txt |
AC |
1395 ms |
84316 KB |
subtask_1_25.txt |
AC |
825 ms |
72028 KB |
subtask_1_26.txt |
AC |
857 ms |
67548 KB |
subtask_1_27.txt |
AC |
1591 ms |
82780 KB |
subtask_1_28.txt |
AC |
1089 ms |
74844 KB |