1651 - Graf

Cerința

Se dă lista muchiilor unui graf neorientat ponderat. Să se determine vârful pentru care media aritmetică a ponderilor muchiilor incidente este minimă. Dacă există mai multe vârfuri cu aceeași medie minimă, se va afișa vârful numerotat cu o valoare mai mică.

Date de intrare

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

Date de ieșire

Programul va afișa pe ecran numărul vf, reprezentând vârful determinat.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

Restricții și precizări

• 1 ≤ n ≤ 100
• ponderile muchiilor sunt numere naturale nenule mai mici decât 1000
• graful dat nu conține noduri izolate

Exemplul 1:

Intrare

5 6
1 2 10
2 3 2
2 5 2
3 5 12
3 4 1
4 5 5

Ieșire

4

Explicație

Mediile ponderilor muchiilor incidente cu vârfurile grafului sunt:

• pentru vârful 1 media este 10
• pentru vârful 2 media este 4.66667
• pentru vârful 3 media este 5
• pentru vârful 4 media este 3
• pentru vârful 5 media este 6.33333

Astfel media minimă este 3, pentru vârful 4

Exemplul 2:

Intrare

101

consola

Datele nu corespund restrictiilor impuse

Rezolvare

from typing import List, Tuple

def check_constraints(n, m, edges):
    if not (1 <= n <= 100):
        return False
    for edge in edges:
        i, j, p = edge
        if not (1 <= i <= n) or not (1 <= j <= n) or not (1 <= p < 1000):
            return False
    return True

def main():
    nMAX = 100
    mat = [[] for _ in range(nMAX + 1)]  # mat[i][0] = (j, p) (edge between i and j with weight p)

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

    if not (1 <= n <= 100):
        print("Detele nu respecta restrictiile impuse")
        return

    edges = [tuple(map(int, input().split())) for _ in range(m)]

    if not check_constraints(n, m, edges):
        print("Detele nu respecta restrictiile impuse")
        return

    for i, j, p in edges:
        mat[i].append((j, p))
        mat[j].append((i, p))

    vfmin = 0
    medmin = float('inf')

    for i in range(1, n + 1):
        _sum = sum(weight for _, weight in mat[i])
        if _sum / len(mat[i]) < medmin:
            medmin = _sum / len(mat[i])
            vfmin = i

    print(vfmin)

if __name__ == "__main__":
    main()