Language: C++

from collections import defaultdict
from heapq import heappop, heappush
class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

def solve():
  n,m = (int(i) for i in input().split())
  route = Graph()
  tmp = [[0]*n for _ in range(n)]
  
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    route.add_edge(a-1,b-1,c)
    route.add_edge(b-1,a-1,c)
    tmp[a-1][b-1] = 1

  
  for i in range(n):
    for j in range(n):
      if not i== j:
        #iを始点としてjに着く経路
        ds = Dijkstra(route,i)
        query = ds.shortest_path(j)
        for k in range(len(query)-1):
            tmp[query[k]][query[k+1]] = 0
  ans = 0
  for i in range(n):
    ans += sum(tmp[i])
  print(ans)
        
solve()

Compiler output:
a.cc:4:7: warning: missing terminating " character
    4 |     """
      |       ^
a.cc:4:7: error: missing terminating " character
a.cc:6:7: warning: missing terminating " character
    6 |     """
      |       ^
a.cc:6:7: error: missing terminating " character
a.cc:22:7: warning: missing terminating " character
   22 |     """
      |       ^
a.cc:22:7: error: missing terminating " character
a.cc:25:7: warning: missing terminating " character
   25 |     """
      |       ^
a.cc:25:7: error: missing terminating " character
a.cc:30:11: error: invalid preprocessing directive #start\U000030ce\U000030fc\U000030c9\U0000304b\U00003089\U0000306e\U00006700\U000077ed\U00008ddd\U000096e2
   30 |         # startノードからの最短距離
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:31:11: error: invalid preprocessing directive #start\U000030ce\U000030fc\U000030c9\U0000306f0
   31 |         # startノードは0, それ以外は無限大で初期化
      |           ^~~~~~~~~~~~~~
a.cc:32:47: warning: multi-character character constant [-Wmultichar]
   32 |         self.dist = defaultdict(lambda: float('inf'))
      |                                               ^~~~~
a.cc:35:11: error: invalid preprocessing directive #\U00006700\U000077ed\U00007d4c\U00008def\U00003067\U0000306e1\U00003064\U0000524d\U0000306e\U000030ce\U000030fc\U000030c9
   35 |         # 最短経路での1つ前のノード
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:38:11: error: invalid preprocessing directive #start\U000030ce\U000030fc\U000030c9\U00003092\U000030ad\U000030e5\U000030fc\U0000306b\U00005165\U0000308c\U0000308b
   38 |         # startノードをキューに入れる
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:43:15: error: invalid preprocessing directive #\U0000512a\U00005148\U00005ea6\U0000ff08\U00008ddd\U000096e2\U0000ff09\U0000304c\U00006700\U00005c0f\U00003067\U00003042\U0000308b\U000030ad\U000030e5\U000030fc\U00003092\U000053d6\U0000308a\U000051fa\U00003059
   43 |             # 優先度（距離）が最小であるキューを取り出す
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:55:11: warning: missing terminating " character
   55 |         """
      |           ^
a.cc:55:11: error: missing terminating " character
a.cc:57:11: warning: missing terminating " character
   57 |         """
      |           ^
a.cc:57:11: error: missing terminating " character
a.cc:61:11: warning: missing terminating " character
   61 |         """
      |           ^
a.cc:61:11: error: missing terminating " character
a.cc:63:11: warning: missing terminating " character
   63 |         """
      |           ^
a.cc:63:11: error: missing terminating " character
a.cc:86:10: error: invalid preprocessing directive #i\U00003092\U000059cb\U000070b9\U00003068\U00003057\U00003066j\U0000306b\U00007740\U0000304f\U00007d4c\U00008def
   86 |         #iを始点としてjに着く経路
      |          ^~~~~~~~~~~~~~~~~~~~~~~~
a.cc:1:1: error: 'from' does not name a type
    1 | from collections import defaultdict
      | ^~~~