# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
56758 | wjoao | Cities (BOI16_cities) | C++11 | 381 ms | 29236 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define maxn 100010
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
long long n, m, k, a, b, c, dist[maxn], ini;
bool is_important[maxn];
vector< pair<long long, long long> > g[maxn];
int main(){
scanf(" %lld %lld %lld", &n, &k, &m);
for(long long i = 0; i < k; i++){
scanf(" %lld", &a);
if( i == 0 ) ini = a;
is_important[a] = true;
}
for(long long i = 0; i < m; i++){
scanf(" %lld %lld %lld", &a, &b, &c);
g[a].push_back({b,c});
g[b].push_back({a,c});
}
memset(dist, inf, sizeof dist);
priority_queue< pair<long long, long long>, vector< pair<long long, long long> >, greater< pair<long long, long long> > > fp;
long long res = 0;
dist[ini] = 0;
fp.push({0, ini});
while(!fp.empty()){
long long d = fp.top().first;
long long v = fp.top().second;
fp.pop();
if(dist[v] < d ) continue;
if(is_important[v]) {
res += dist[v];
dist[v] = 0;
}
for(long long i = 0; i < g[v].size(); i++){
long long u = g[v][i].first;
long long d2 = g[v][i].second;
if( dist[v] + d2 < dist[u] ){
dist[u] = dist[v] + d2;
fp.push({dist[u], u});
}
}
}
printf("%lld\n", res);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |