# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
879456 | KN200711 | Cities (BOI16_cities) | C++14 | 328 ms | 27556 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 ll long long
# define fi first
# define se second
using namespace std;
vector< pair<int, ll> > edge[100001];
ll dist[100001], mn[5][100001];
bool vis[100001];
int main() {
int N, K, M;
scanf("%d %d %d", &N, &K, &M);
vector<int> ipr(K);
for(int i=0;i<K;i++) {
scanf("%d", &ipr[i]);
}
for(int i=0;i<M;i++) {
int a, b;
ll c;
scanf("%d %d %lld", &a, &b, &c);
edge[a].push_back(make_pair(b, c));
edge[b].push_back(make_pair(a, c));
}
for(int i=0;i<K;i++) {
priority_queue< pair<ll, int> > PQ;
PQ.push(make_pair(0ll, ipr[i]));
for(int c=1;c<=N;c++) vis[c] = 0;
while(!PQ.empty()) {
ll a = PQ.top().fi;
int b = PQ.top().se;
PQ.pop();
if(vis[b]) continue;
vis[b] = 1;
mn[i][b] = -a;
dist[b] -= a;
for(int c=0;c<edge[b].size();c++) {
if(!vis[edge[b][c].fi]) PQ.push(make_pair(a - 1ll * edge[b][c].se, edge[b][c].fi));
}
}
}
ll ans = 1e18;
for(int d=1;d<=N;d++) {
ans = min(ans, dist[d]);
}
if(K == 4) {
for(int i=1;i<=N;i++) {
for(int c=0;c<4;c++) {
ll as = 0ll, v= 1e18;
for(int d=0;d<4;d++) {
if(c == d) continue;
v = min(v, mn[d][ipr[c]]);
as += mn[d][i];
}
as += v;
ans = min(ans, as);
}
}
}
printf("%lld\n", ans);
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... |