Seduta Plenaria 96/100

#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll N, M, K;

int main() {

    ios::sync_with_stdio(0);
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w",stdout);

    cin >> N >> M >> K;

    ll Indici[K], Pigrizia[K];
    for(auto &i : Indici) cin >> i;
    for(auto &i : Pigrizia) cin >> i;

    vector <pair <ll, ll>> Adj[N];

    for(ll i = 0; i < M; i++) {

        ll a, b, c; cin >> a >> b >> c;

        Adj[a].push_back({b, c});
        Adj[b].push_back({a, c});
    }

    ll Risultati[N];
    memset(Risultati, 0, sizeof(Risultati));

    for(ll i = 0; i < K; i++) {

        priority_queue <pair <ll, ll>> Q;

        bool V[N];
        ll D[N];

        memset(D, 0x3f, sizeof(D));
        D[Indici[i]] = 0;

        memset(V, 0, sizeof(V));

        Q.push({0, Indici[i]});

        while(!Q.empty()) {

            ll a = Q.top().second; Q.pop();

            if(V[a]) continue;
            V[a] = 1;

            for(auto j : Adj[a]) {

                ll b = j.first, w = j.second;

                if(D[a]+w < D[b]) {

                    D[b] = D[a] + w;
                    Q.push({-D[b], b});
                }
            }
        }

        for(ll j = 0; j < N; j++) {

            Risultati[j] += D[j] * Pigrizia[i];
        }
    }

    pair <ll, ll> Res;
    Res.first = -1;
    Res.second = 999999999;

    for(ll i = 0; i < N; i++) {

        if(Risultati[i] < Res.second) {

            Res.first = 1;
            Res.second = Risultati[i];
        } else if(Risultati[i] == Res.second) Res.first++;
    }

    cout << Res.first << "\n" << Res.second;

}

Buon pomeriggio. Questa volta mi trovo alle prese con il problema Seduta Plenaria e ricevo un output errato all’ultimo testcase. L’idea di per se penso che sia giusta (uso Dijkstra in ogni nodo in cui è presente una commissione ed infine trovo il minimo nel vettore risultati), però evidentemente c’è qualcosa che mi sfugge. Grazie in anticipo.

Ciao, con long long il limite superiore per trovare il minore non è sufficiente.

Ho provato ad usare anche unsigned long long ma mi da comunque lo stesso risultato.

Il problema non è il tipo ma il valore limite assegnato alla variabile Res per determinare il minore.

Si infatti mentre lo stavi scrivendo me ne ero accorto ora provo a cambiare.

Ok funziona grazie e scusa il disturbo.