| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 261752 |
2020-08-12T04:19:55 Z |
Autoratch |
Cities (BOI16_cities) |
C++14 |
|
2037 ms |
25188 KB |
#include <bits/stdc++.h>
using namespace std;
#define pii pair<long long,int>
const int N = 1e5 + 1;
const int K = 6;
int n,m,k;
vector<pair<int,int> > adj[N];
vector<int> imp;
int idx[N];
bool visited[N],used[K][K];
long long dist[K][N],dis1[N],dist1[K][K][N],dis2[N],ans = LLONG_MAX;
priority_queue<pii,vector<pii>,greater<pii> > q;
void dijk(int x,long long (&dist)[N])
{
for(int i = 1;i <= n;i++) visited[i] = false,dist[i] = LLONG_MAX;
dist[x] = 0;
q.push({0,x});
while(!q.empty())
{
int u = q.top().second;
q.pop();
if(visited[u]) continue;
visited[u] = true;
for(auto [w,v] : adj[u]) if(dist[u]+w<dist[v]) dist[v] = dist[u]+w,q.push({dist[v],v});
}
}
long long cal(int a,int b)
{
if(idx[a]) return dist[idx[a]][b];
else return dist[idx[b]][a];
}
void solve2(){ ans = min(ans,cal(imp[0],imp[1])); }
void solve3()
{
for(int i = 1;i <= n;i++)
{
long long each = 0;
for(int x : imp) each+=cal(i,x);
ans = min(ans,each);
}
}
void dijktwo()
{
for(int i = 1;i <= n;i++) q.push({dis1[i],i}),visited[i] = false;
while(!q.empty())
{
int u = q.top().second;
q.pop();
if(visited[u]) continue;
visited[u] = true;
for(auto [w,v] : adj[u]) if(dis1[u]+w<dis1[v]) dis1[v] = dis1[u]+w,q.push({dis1[v],v});
}
}
void solve4()
{
long long each = 0;
for(int i = 0;i < k-1;i++) each+=cal(imp[i],imp[i+1]);
ans = min(ans,each);
for(int i = 1;i <= n;i++) ans = min(ans,cal(imp[0],imp[1])+cal(imp[1],i)+cal(imp[2],i)+cal(imp[3],i));
for(int i = 1;i <= n;i++) dis1[i] = cal(imp[0],i)+cal(imp[1],i),dis2[i] = cal(imp[2],i)+cal(imp[3],i);
dijktwo();
for(int i = 1;i <= n;i++) ans = min(ans,dis1[i]+dis2[i]);
}
void solve5s()
{
for(int i = 1;i <= n;i++) dis1[i] = cal(imp[0],i)+cal(imp[1],i),dis2[i] = cal(imp[2],i)+cal(imp[3],i)+cal(imp[4],i);
dijktwo();
for(int i = 1;i <= n;i++) dist1[idx[imp[0]]][idx[imp[1]]][i] = dis1[i];
}
void solve5()
{
long long each = 0;
for(int i = 0;i < k-1;i++) each+=cal(imp[i],imp[i+1]);
ans = min(ans,each);
ans = min(ans,cal(imp[0],imp[1])+cal(imp[0],imp[2])+cal(imp[0],imp[3])+cal(imp[3],imp[4]));
for(int i = 1;i <= n;i++)
{
ans = min(ans,cal(imp[0],i)+cal(imp[1],i)+cal(imp[2],i)+cal(imp[3],i)+cal(imp[3],imp[4]));
ans = min(ans,cal(imp[0],imp[1])+cal(imp[1],i)+cal(imp[2],i)+cal(imp[3],i)+cal(imp[4],imp[3]));
ans = min(ans,cal(imp[0],imp[1])+cal(imp[1],imp[2])+cal(imp[2],i)+cal(imp[3],i)+cal(imp[4],i));
ans = min(ans,cal(imp[0],imp[2])+cal(imp[2],imp[1])+cal(imp[2],i)+cal(i,imp[3])+cal(imp[4],imp[3]));
ans = min(ans,cal(imp[0],i)+cal(imp[1],i)+cal(imp[2],i)+cal(imp[3],imp[2])+cal(imp[4],imp[2]));
ans = min(ans,cal(imp[0],i)+cal(imp[1],i)+cal(imp[2],imp[1])+cal(imp[3],imp[1])+cal(imp[4],imp[3]));
}
if(imp[0]<imp[1] and !used[idx[imp[0]]][idx[imp[1]]]) used[idx[imp[0]]][idx[imp[1]]] = true,solve5s();
for(int i = 1;i <= n;i++) dis2[i] = cal(imp[2],i)+cal(imp[3],i)+cal(imp[4],i);
for(int i = 1;i <= n;i++) ans = min(ans,dist1[idx[imp[0]]][idx[imp[1]]][i]+dis2[i]);
for(int i = 1;i <= n;i++) dis2[i] = cal(imp[2],imp[3])+cal(imp[3],i)+cal(imp[4],i);
for(int i = 1;i <= n;i++) ans = min(ans,dist1[idx[imp[0]]][idx[imp[1]]][i]+dis2[i]);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> k >> m;
for(int i = 1;i <= k;i++)
{
int x;
cin >> x;
imp.push_back(x);
idx[x] = i;
}
for(int i = 0;i < m;i++)
{
int a,b,d;
cin >> a >> b >> d;
adj[a].push_back({d,b});
adj[b].push_back({d,a});
}
for(int x : imp) dijk(x,dist[idx[x]]);
sort(imp.begin(),imp.end());
do
{
if(k==2) solve2();
else if(k==3) solve3();
else if(k==4) solve4(),solve3();
else solve5(),solve3();
}while(next_permutation(imp.begin(),imp.end()));
cout << ans;
}
Compilation message
cities.cpp: In function 'void dijk(int, long long int (&)[100001])':
cities.cpp:27:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [w,v] : adj[u]) if(dist[u]+w<dist[v]) dist[v] = dist[u]+w,q.push({dist[v],v});
^
cities.cpp: In function 'void dijktwo()':
cities.cpp:58:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [w,v] : adj[u]) if(dis1[u]+w<dis1[v]) dis1[v] = dis1[u]+w,q.push({dis1[v],v});
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
2816 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
269 ms |
12528 KB |
Output is correct |
| 2 |
Correct |
261 ms |
12564 KB |
Output is correct |
| 3 |
Correct |
114 ms |
8444 KB |
Output is correct |
| 4 |
Correct |
86 ms |
7416 KB |
Output is correct |
| 5 |
Correct |
223 ms |
11756 KB |
Output is correct |
| 6 |
Correct |
84 ms |
7380 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2944 KB |
Output is correct |
| 2 |
Correct |
11 ms |
2944 KB |
Output is correct |
| 3 |
Correct |
9 ms |
2816 KB |
Output is correct |
| 4 |
Correct |
7 ms |
2944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2037 ms |
18156 KB |
Output is correct |
| 2 |
Correct |
1992 ms |
17620 KB |
Output is correct |
| 3 |
Correct |
1511 ms |
12904 KB |
Output is correct |
| 4 |
Correct |
1049 ms |
13160 KB |
Output is correct |
| 5 |
Correct |
248 ms |
8696 KB |
Output is correct |
| 6 |
Correct |
99 ms |
9080 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1345 ms |
25188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
