Submission #1517278

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;

    vector<vector<int> > connect(N, vector<int>(N, -1));

    REP (i, M) {
        int u, v, l;
        cin >> u >> v >> l;
        u--;
        v--;
        connect[u][v] = l;
        connect[v][u] = l;
    }

    long long ans = INT_MAX;
    REP (i, N) {
        //繋がってなかったら無視
        if (connect[0][i] == -1)
            continue;

        //繋がってたら移動して,その道を除去
        //そうしてから0への最短経路を求める
        long long distance = connect[i][0];
        connect[i][0] = -1;

        priority_queue<int> pq;
        pq.push(i);
        vector<long long> cost(N, INT_MAX);
        cost[i] = 0;
        while (!pq.empty()) {
            int curr = pq.top();
            pq.pop();
            //printf("curr = %d\n", curr);

            REP (j, N) {
                if (connect[curr][j] == -1)
                    continue;

                long long new_cost = cost[curr] + connect[curr][j];
                if (new_cost < cost[j]) {
                    cost[j] = new_cost;
                    pq.push(j);
                }
            }
        }

        //REP (k, N) printf("cost[%d] = %lld\n", k, cost[k]);
        
        //復元
        connect[i][0] = distance;
        distance += cost[0];
        //printf("distance = %lld\n", distance);
        ans = min(ans, distance);

    }

    if (ans != INT_MAX)
        cout << ans << endl;
    else
        cout << -1 << endl;
}

Submission Info

Judge Result