| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1012758 |
2024-07-02T14:43:23 Z |
hengliao |
Cities (BOI16_cities) |
C++17 |
|
388 ms |
72688 KB |
#include<bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
const ll mxN=2e5+5;
const ll inf=1e18;
ll n, m, k;
vector<pll> adj[mxN];
vector<pair<ll, pll>> edges;
ll dis[mxN][5];
ll con[5];
ll dsu[21];
ll tepdis[1005][1005];
ll find_set(ll a){
if(dsu[a]<0) return a;
return dsu[a]=find_set(dsu[a]);
}
void unite(ll a, ll b){
ll f=find_set(a);
ll s=find_set(b);
if(abs(dsu[f])<abs(dsu[s])){
swap(f, s);
}
dsu[f]+=dsu[s];
dsu[s]=f;
}
bool visited[mxN];
void solve(){
cin>>n>>k>>m;
for(ll i=0;i<k;i++){
cin>>con[i];
}
for(ll i=0;i<m;i++){
ll u, v, w;
cin>>u>>v>>w;
adj[u].pb({v, w});
adj[v].pb({u, w});
edges.pb({w, {u, v}});
}
sort(edges.begin(), edges.end());
if(n<=20){
ll ans=inf;
for(ll mask=0;mask<(1LL<<n);mask++){
bool good=1;
for(ll i=0;i<k;i++){
if((mask&(1LL<<(con[i]-1)))==0){
good=0;
}
}
memset(dsu, -1, sizeof(dsu));
ll cur=0;
for(auto &edge:edges){
ll w=edge.F;
ll u=edge.S.F;
ll v=edge.S.S;
if((mask&(1LL<<(u-1)))==0 || (mask&(1LL<<(v-1)))==0){
continue;
}
if(find_set(u)!=find_set(v)){
cur+=w;
unite(u, v);
}
}
for(ll i=1;i<k;i++){
if(find_set(con[0])!=find_set(con[i])){
good=0;
}
}
if(good) ans=min(ans, cur);
}
cout<<ans<<'\n';
return;
}
if(k==2){
//memset(visited, 0, sizeof(visited));
memset(dis, -1, sizeof(dis));
priority_queue<pll, vector<pll>, greater<pll>> pq;
pq.push({0, con[0]});
while(!pq.empty()){
pll cur=pq.top(); pq.pop();
if(dis[cur.S][0]!=-1) continue;
dis[cur.S][0]=cur.F;
for(auto &[x, y]:adj[cur.S]){
pq.push({cur.F+y, x});
}
}
cout<<dis[con[1]][0]<<'\n';
return;
}
else if(k==3){
memset(dis, -1, sizeof(dis));
for(ll i=0;i<3;i++){
priority_queue<pll, vector<pll>, greater<pll>> pq;
pq.push({0, con[i]});
while(!pq.empty()){
pll cur=pq.top(); pq.pop();
if(dis[cur.S][i]!=-1) continue;
dis[cur.S][i]=cur.F;
for(auto &[x, y]:adj[cur.S]){
pq.push({cur.F+y, x});
}
}
}
ll ans=inf;
for(ll i=1;i<=n;i++){
ans=min(ans, dis[i][0]+dis[i][1]+dis[i][2]);
}
cout<<ans<<'\n';
return;
}
else if(k==4){
memset(dis, -1, sizeof(dis));
for(ll i=0;i<4;i++){
priority_queue<pll, vector<pll>, greater<pll>> pq;
pq.push({0, con[i]});
while(!pq.empty()){
pll cur=pq.top(); pq.pop();
if(dis[cur.S][i]!=-1) continue;
dis[cur.S][i]=cur.F;
for(auto &[x, y]:adj[cur.S]){
pq.push({cur.F+y, x});
}
}
}
ll ans=inf;
for(ll i=1;i<=n;i++){
/*cout<<i<<' '<<dis[i][0]+dis[i][1]+dis[i][2]+dis[i][3]<<'\n';
for(ll j=0;j<4;j++){
cout<<dis[i][j]<<' ';
}
cout<<'\n';*/
ans=min(ans, dis[i][0]+dis[i][1]+dis[i][2]+dis[i][3]);
}
//cout<<ans<<'\n';
for(ll ex=0;ex<4;ex++){
ll mn=inf;
for(ll i=0;i<4;i++){
if(i==ex){
continue;
}
mn=min(mn, dis[con[i]][ex]);
}
for(ll mid=1;mid<=n;mid++){
ll tep=0;
for(ll i=0;i<4;i++){
if(i==ex) continue;
tep+=dis[mid][i];
}
tep+=mn;
ans=min(ans, tep);
}
}
memset(tepdis, -1, sizeof(tepdis));
for(ll i=1;i<=n;i++){
priority_queue<pll, vector<pll>, greater<pll>> pq;
pq.push({0, i});
while(!pq.empty()){
pll cur=pq.top(); pq.pop();
if(tepdis[cur.S][i]!=-1) continue;
tepdis[cur.S][i]=cur.F;
for(auto &[x, y]:adj[cur.S]){
pq.push({cur.F+y, x});
}
}
}
for(ll i=1;i<4;i++){
for(ll mid1=1;mid1<=n;mid1++){
for(ll mid2=1;mid2<=n;mid2++){
ll tep1=dis[mid1][0]+dis[mid1][i];
ll tep2=0;
for(ll j=1;j<4;j++){
if(j==i) continue;
tep2+=dis[mid2][j];
}
ans=min(ans, tep1+tep2+tepdis[mid1][mid2]);
}
}
}
cout<<ans<<'\n';
return;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
148 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
134 ms |
6540 KB |
Output is correct |
| 4 |
Correct |
140 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
143 ms |
6492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
280 ms |
34608 KB |
Output is correct |
| 2 |
Correct |
313 ms |
34104 KB |
Output is correct |
| 3 |
Correct |
71 ms |
20480 KB |
Output is correct |
| 4 |
Correct |
233 ms |
40876 KB |
Output is correct |
| 5 |
Correct |
161 ms |
34668 KB |
Output is correct |
| 6 |
Correct |
117 ms |
38628 KB |
Output is correct |
| 7 |
Correct |
7 ms |
13144 KB |
Output is correct |
| 8 |
Correct |
5 ms |
13148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
363 ms |
21088 KB |
Output is correct |
| 2 |
Correct |
350 ms |
21328 KB |
Output is correct |
| 3 |
Correct |
79 ms |
20828 KB |
Output is correct |
| 4 |
Correct |
171 ms |
21080 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
388 ms |
72688 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
86 ms |
21488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
