Editing 1652 - RF


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

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

= Date de ieșire =
Programul va afișa pe ecran numărul <code>C</code>, reprezentând valoare cerută.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* costurile arcelor vor fi mai mici decât <code>1000</code>

= 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 <code>4</code> arce sunt: <code>(2 3)</code>, <code>(3 5)</code>, <code>(4 1)</code> și <code>(5 4)</code>.

== 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>