| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1012776 |
2024-07-02T15:07:31 Z |
hengliao |
Cities (BOI16_cities) |
C++17 |
|
570 ms |
49560 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 dis2[mxN];
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++){
memset(dis2, -1, sizeof(dis2));
priority_queue<pll, vector<pll>, greater<pll>> pq;
priority_queue<pll, vector<pll>, greater<pll>> pq2;
for(ll j=1;j<=n;j++){
pq.push({dis[j][0]+dis[j][i], j});
}
while(!(pq.empty() && pq2.empty())){
pll cur1={inf, inf};
pll cur2={inf, inf};
if(!pq.empty()){
cur1=pq.top();
}
if(!pq2.empty()){
cur2=pq2.top();
}
pll cur;
if(cur1.F<cur2.F){
pq.pop();
cur.F=cur1.F;
cur.S=cur1.S;
}
else{
pq2.pop();
cur.F=cur2.F;
cur.S=cur2.S;
}
if(dis2[cur.S]!=-1) continue;
dis2[cur.S]=cur.F;
for(auto &[x, y]:adj[cur.S]){
pq2.push({cur.F+y, x});
}
}
for(ll mid=1;mid<=n;mid++){
ll tep=dis2[mid];
for(ll j=1;j<4;j++){
if(j==i) continue;
tep+=dis[mid][j];
}
ans=min(ans, tep);
}
}
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 |
1 ms |
5980 KB |
Output is correct |
| 2 |
Correct |
132 ms |
8096 KB |
Output is correct |
| 3 |
Correct |
135 ms |
6052 KB |
Output is correct |
| 4 |
Correct |
133 ms |
5980 KB |
Output is correct |
| 5 |
Correct |
141 ms |
5976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
304 ms |
34604 KB |
Output is correct |
| 2 |
Correct |
309 ms |
34044 KB |
Output is correct |
| 3 |
Correct |
70 ms |
20476 KB |
Output is correct |
| 4 |
Correct |
239 ms |
40804 KB |
Output is correct |
| 5 |
Correct |
142 ms |
35908 KB |
Output is correct |
| 6 |
Correct |
116 ms |
38672 KB |
Output is correct |
| 7 |
Correct |
6 ms |
13144 KB |
Output is correct |
| 8 |
Correct |
7 ms |
13144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14684 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14684 KB |
Output is correct |
| 3 |
Correct |
6 ms |
14680 KB |
Output is correct |
| 4 |
Correct |
9 ms |
14684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
570 ms |
37724 KB |
Output is correct |
| 2 |
Correct |
547 ms |
41440 KB |
Output is correct |
| 3 |
Correct |
172 ms |
29148 KB |
Output is correct |
| 4 |
Correct |
523 ms |
42736 KB |
Output is correct |
| 5 |
Correct |
489 ms |
45920 KB |
Output is correct |
| 6 |
Correct |
483 ms |
49560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
21032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
