oj.uz

Submission #968841

# Submission time Handle Problem Language Result Execution time Memory
968841 2024-04-24T07:25:38 Z vjudge1 Cities (BOI16_cities) C++17
0 / 100
 3974 ms 13644 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5 + 5;
const int INF = 1e9 + 7;

//           node weight
vector <pair <int, int>> adj[MAX_N];
int min_dist[MAX_N];
//          node
vector<int> imp;


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, k, m;
    cin >> n >> k >> m;
    while(k--){
        int im; cin>>im;
        imp.emplace_back(im);
    }
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].emplace_back(b,c);
        adj[b].emplace_back(a,c);
    }

    
    long long ans = INT_MAX;
    for (int S = 1; S <= n; S++){
    // pq for keeping the pair of (distance, node)
        for (int i = 1; i <= n; i++) min_dist[i] = INF;
        priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> pq;
        pq.emplace(0, S);
        min_dist[S] = 0;
        while (!pq.empty()) {
            auto [cur_dis, u] = pq.top();
            pq.pop();

            if (cur_dis > min_dist[u]){
                // cout<<"con: "<<cur_dis<<' '<<min_dist[u]<<' '<<u<<endl;
                continue;
            }
        
            for (auto [adj_ver, adj_w] : adj[u]) {
                if (min_dist[u] + adj_w < min_dist[adj_ver]) { // if the new path is shorter (better), replace and use the new one.
                    min_dist[adj_ver] = min_dist[u] + adj_w;
                    pq.emplace(min_dist[adj_ver], adj_ver);
                    // cout<<u<<" emplace: "<<adj_ver<<' '<<min_dist[adj_ver]<<endl;
                }
            }
        }
        long long sum= 0;
        for(auto i:imp){
            sum+=min_dist[i];
        }
        ans = min(ans,sum);
        // cerr<<"sum "<<sum<<"\n";
        // for (int i = 1-1; i <= N-1; i++) {
        //     if (min_dist[i] == INF) cout << "-1 "; // the path does not exist
        //     else cout << min_dist[i] << ' ';
        // }
    }
    cout<<ans<<"\n";
    return 0;
}

Subtask #1
0 / 22.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3889 ms 13644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 3805 ms 13640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 3974 ms 13640 KB Output isn't correct
2 Halted 0 ms 0 KB -