Cerința

Se dă un graf orientat în care arcele au asociate costuri (numere naturale nenule). Să se determine câte arce (x,y) din graf au costul egal cu costul drumului de cost minim de la x la y.

Date de intrare

Programul citește de la tastatură numerele n m, reprezentând numărul de vârfuri și numărul de arce din graf, apoi m triplete i j p, reprezentând arcele, date prin extremități și cost.

Date de ieșire

Programul va afișa pe ecran numărul C, reprezentând valoare cerută.

Restricții și precizări

1 ≤ n ≤ 100
costurile arcelor vor fi mai mici decât 1000

Exemplu:

Intrare

Ieșire

Explicație

Cele 4 arce sunt: (2 3), (3 5), (4 1) și (5 4).

Rezolvare

<syntaxhighlight lang="python3"> import sys

def floyd_warshall(n, dist):

   for k in range(n):
       for i in range(n):
           for j in range(n):
               if dist[i][k] + dist[k][j] < dist[i][j]:
                   dist[i][j] = dist[i][k] + dist[k][j]

def main():

   n, m = map(int, input().split())

   inf = float('inf')
   dist = [[inf] * n for _ in range(n)]

   edges = []
   for _ in range(m):
       u, v, p = map(int, input().split())
       u -= 1
       v -= 1
       dist[u][v] = p
       edges.append((u, v, p))

   for i in range(n):
       dist[i][i] = 0

   floyd_warshall(n, dist)

   count = 0
   for u, v, p in edges:
       if dist[u][v] == p:
           count += 1

   print(count)

if __name__ == "__main__":

   main()

</syntaxhighlight>