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.

Restricții și precizări

• 1 ≤ n ≤ 100
• ponderile muchiilor sunt numere naturale nenule mai mici decât 1000

Exemplu

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

#include <bits/stdc++.h>
using namespace std;

struct poz
{
    int cnt , val;
    double pon;
}G[1001];
int n , m , rez , mini =99999999;

int main()
{
    cin >> n >> m;
    int x , y , w;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y >> w;
        G[x].cnt++;
        G[y].cnt++;
        G[x].val += w;
        G[y].val += w;
    }
    for(int i = 1 ; i <= n ; i++)
        G[i].pon = G[i].val / G[i].cnt;

    for(int i = 1 ; i <= n ; i++)
        if(G[i].pon < mini)
        {
            mini = G[i].pon;
            rez = i;
        }
    cout << rez;
}