Submission #484137

#	Time	Username	Problem	Language	Result	Execution time	Memory
484137		alireza_kaviani	Cities (BOI16_cities)	C++11	0 / 100	337 ms	23840 KiB

cities

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const ll N = 2e5 + 10, inf = 1e18;
 
int a[N];
ll d[N];
int par[N];
bool mark[N];
 
vector<pair<int, ll> > G[N];
 
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, k, m;
    cin >>n >>k >>m;
    for(int i = 1; i <= k; i++) {
        cin >>a[i];
        mark[a[i]] = 1;
    }
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        cin >>u >>v >>w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
     
    for(int i = 1; i <= n; i++)
        d[i] = inf;
 
    ll ans = 0;
    set<pair<ll, int> > st;
    st.insert({0, a[1]});
    d[a[1]] = 0;
    par[a[1]] = a[1];
    while(!st.empty()) {
        int p = st.begin() -> second;
        st.erase(st.begin());
        if(mark[p]) {
            int w = par[p];
            while(!mark[w]) {
                st.erase({d[w], w});
                st.insert({0, w});
                d[w] = 0;
                w = par[w];
            }
            ans += d[p];
            d[p] = 0;
        }
        for(auto i : G[p]) {
            if(d[i.first] > d[p] + i.second) {
                par[i.first] = p;
                st.erase({d[i.first], i.first});
                d[i.first] = d[p] + i.second;
                st.insert({d[i.first], i.first});
            }
        }
    }
    cout<<ans;
}

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