Submission #745784

#	Time	Username	Problem	Language	Result	Execution time	Memory
745784		vjudge1	Cities (BOI16_cities)	C++17	0 / 100	4 ms	5204 KiB

cities

#include <bits/stdc++.h>

using namespace std;
using ll = long long int;

const ll mod = 1e9 + 7;

const ll inf = 1e16;

vector<pair<int, ll>> g[100100];

ll adj[110][110] = {0};
ll d[110][110] = {0};

int main(){
    int n, k, m;
    cin >> n >> k >> m;
    vector<int> imp(k);
    for(auto& i : imp){
        cin >> i;
    }
    while(m--){
        ll a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
        adj[a][b] = adj[b][a] = w;
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            if(i == j) continue;
            d[i][j] = adj[i][j] ==  0 ? inf : adj[i][j];
        }
    }
    for(int p = 1; p <= n; ++p){
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                if(d[i][p] == inf || d[p][j] == inf){
                    continue;
                }
                d[i][j] = min(d[i][j], d[i][p] + d[p][j]);
            }
        }
    }
    ll sol = inf;
    for(int i = 1; i <= n; ++i){
        ll a = 0;
        for(auto j : imp){
            a += d[i][j];
        }
        sol = min(sol, a);
    }
    cout << sol << endl;
    return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26