| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1012773 |
2024-07-02T15:06:24 Z |
hengliao |
Cities (BOI16_cities) |
C++17 |
|
365 ms |
77552 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 |
2 ms |
8024 KB |
Output is correct |
| 2 |
Correct |
129 ms |
8028 KB |
Output is correct |
| 3 |
Correct |
128 ms |
8120 KB |
Output is correct |
| 4 |
Correct |
131 ms |
8276 KB |
Output is correct |
| 5 |
Correct |
130 ms |
8100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
291 ms |
40540 KB |
Output is correct |
| 2 |
Correct |
265 ms |
40504 KB |
Output is correct |
| 3 |
Correct |
62 ms |
24392 KB |
Output is correct |
| 4 |
Correct |
217 ms |
46952 KB |
Output is correct |
| 5 |
Correct |
148 ms |
40688 KB |
Output is correct |
| 6 |
Correct |
109 ms |
43508 KB |
Output is correct |
| 7 |
Correct |
4 ms |
14424 KB |
Output is correct |
| 8 |
Correct |
4 ms |
14368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
351 ms |
22676 KB |
Output is correct |
| 2 |
Correct |
330 ms |
22608 KB |
Output is correct |
| 3 |
Correct |
79 ms |
22588 KB |
Output is correct |
| 4 |
Correct |
183 ms |
22724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
365 ms |
77552 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
80 ms |
27132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
