Danciu: Pagină nouă: = 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 extre...

2024-06-03T22:35:12Z

Pagină nouă: = 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 extre...

New page

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

1652 - RF - Revision history