Submission #253112

#TimeUsernameProblemLanguageResultExecution timeMemory
253112Adhyyan1252Cities (BOI16_cities)C++11
100 / 100
1676 ms47668 KiB
#include<bits/stdc++.h> //12 48 using namespace std; #define int long long #define INF 1e17 typedef pair<int, int> ii; template <typename T> using vv = vector<vector<T> >; struct edge{ int u, v, c; }; int n, k, m; vector<int> h; vv<int> g; vector<edge> e; vector<vector<int> > dh; void dijkstra1(int val){ //val is the index of the impp array int source = h[val]; dh[val] = vector<int>(n, INF); priority_queue<ii> q; q.push({0, source}); while(!q.empty()){ pair<int, int> t = q.top(); q.pop(); if(dh[val][t.second] != INF){ assert(dh[val][t.second] <= -t.first); continue; } dh[val][t.second] = -t.first; for(int eid: g[t.second]){ int next = e[eid].u + e[eid].v - t.second; if(dh[val][next] == INF){ q.push({t.first - e[eid].c, next}); }else{ assert(dh[val][next] <= (-t.first + e[eid].c)); } } } } vector<vector<vector<int> > > dab; signed main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>k>>m; h.resize(k); for(int i = 0; i < k; i++){ cin>>h[i]; h[i]--; } g.resize(n); for(int i = 0; i < m; i++){ int a, b, c; cin>>a>>b>>c; a--, b--; e.push_back({a, b, c}); g[a].push_back(i); g[b].push_back(i); } //find shortest path from all important to all others dh.resize(k); for(int i = 0; i < k; i++){ dijkstra1(i); } //d[a][b][i] short distance from i to a and i to b dab = vector<vector<vector<int> > > (k, vector<vector<int> > (k, vector<int>(n, INF))); for(int a = 0; a < k; a++){ for(int b = 0; b < k; b++){ if(a == b){ dab[a][a] = dh[a]; }else{ for(int i = 0; i < n; i++){ dab[a][b][i] = dh[a][i] + dh[b][i]; } } } } //do multisource dijkstra from for(int a = 0; a < k; a++){ for(int b = a+1; b < k; b++){ //make dab[a][b][i] the best value for i vector<int> vis(n, 0); priority_queue<ii> q; for(int i = 0; i < n; i++){ q.push({-dab[a][b][i], i}); } while(!q.empty()){ ii t = q.top(); q.pop(); if(vis[t.second]) { assert(-t.first >= dab[a][b][t.second]); continue; } vis[t.second] = 1; assert(dab[a][b][t.second] >= -t.first); dab[a][b][t.second] = -t.first; for(int eid: g[t.second]){ int next = e[eid].u + e[eid].v - t.second; if(dab[a][b][next] > (-t.first + e[eid].c)){ q.push({t.first - e[eid].c, next}); assert(vis[next] == 0); } } } } } int bestAns = LONG_LONG_MAX; //find answer if(k < 5){ for(int i = 0; i < n; i++){ vector<int> perm(k); for(int j = 0; j < k; j++) perm[j] = j; do{ int curAns = 0; for(int j = 0; j < k; j += 2){ if(j == k-1){ curAns += dab[perm[j]][perm[j]][i]; }else{ int fir = perm[j], sec = perm[j+1]; if(fir > sec) swap(fir, sec); curAns += dab[fir][sec][i]; } } bestAns = min(bestAns, curAns); }while(next_permutation(perm.begin(), perm.end())); } }else{ for(int c = 0; c < 5; c++){ int f1 = c==0?1:0; for(int f2 = 0; f2 < 5; f2++){ if(f2 == f1 || f2 == c) continue; int o1 = -1, o2 = -1; for(o1 = 0; o1 < 5; o1++) if(o1 != f1 && o1 != f2 && o1 != c) break; o2 = 10 - (c + f1 + f2 + o1); for(int i = 0; i < n; i++){ assert(f1 < f2); assert(o1 < o2); bestAns = min(bestAns, dab[c][c][i] + dab[f1][f2][i] + dab[o1][o2][i]); } } } } cout<<bestAns<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...