oj.uz

Submission #484137

# Submission time Handle Problem Language Result Execution time Memory
484137 2021-11-02T07:35:37 Z alireza_kaviani Cities (BOI16_cities) C++11
0 / 100
 337 ms 23840 KB 
#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.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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