1652 - RF

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

5 7
2 1 10
2 3 2
3 1 10
3 4 3
3 5 1
4 1 2
5 4 1

Ieșire

4

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>