oj.uz

Submission #745789

# Submission time Handle Problem Language Result Execution time Memory
745789 2023-05-21T07:47:32 Z vjudge1 Cities (BOI16_cities) C++17
0 / 100
 87 ms 5524 KB 
#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;
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            if(i == j) continue;
            d[i][j] = inf;
        }
    }
    while(m--){
        ll a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
        d[a][b] = d[b][a] = min(w, d[a][b]);
    }
    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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Incorrect 2 ms 2644 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 78 ms 5512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 5460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 5524 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 87 ms 5508 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -