Submission #701655

#	Time	Username	Problem	Language	Result	Execution time	Memory
701655		karrigan	Relay Marathon (NOI20_relaymarathon)	C++17	17 / 100	6066 ms	207320 KiB

RelayMarathon

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+9;
const long long inf=1e13;
struct edg{
int v;
long long w;
};
vector<edg>a[maxn];
vector<int>bit[2];
int b[maxn];
struct suzy{
int u;
long long w;
int lena;
bool operator < (const suzy &p)const {
return w>p.w;
}
};
int n,m,k;
long long dis[maxn];
int vis[maxn];
pair<long long,int>d[maxn][21];
int x=0,y=0,fix=0,fiy=0;
long long another=inf;
void sp(int bt){
if (bit[0].empty()||bit[1].empty())return;
for (int i=1;i<=n;i++){
    dis[i]=inf;
    vis[i]=0;
}
priority_queue<suzy>c;
for (auto v:bit[0]){
    c.push({v,0,v});
    dis[v]=0;
}
while (!c.empty()){
    auto u=c.top();
    c.pop();
    if (vis[u.u]==1)continue;
    vis[u.u]=1;
    if (u.w!=0)d[u.u][bt]={u.w,u.lena};
    //cerr<<u.lena<<'\n';
    for (auto v:a[u.u]){
        long long newdis=u.w+v.w;
        if (newdis<dis[v.v]){
            dis[v.v]=newdis;
            c.push({v.v,newdis,u.lena});
        }
    }
}
}
struct yoonjung{
int u;
long long w;
bool operator < (const yoonjung &p)const {
return w>p.w;
}
};
long long p[maxn][2];
int vi[maxn];
long long prefix[maxn];
long long suffix[maxn];
void anothersp(int u1,int t){
for (int i=1;i<=n;i++){
    p[i][t]=inf;
    vi[i]=0;
}
p[u1][t]=0;
priority_queue<yoonjung>c;
c.push({u1,0});
while (!c.empty()){
    auto u=c.top();
    c.pop();
    if (vi[u.u])continue;
    vi[u.u]=1;
    for (auto v:a[u.u]){
        long long newdis=u.w+v.w;
        if (p[v.v][t]>newdis){
            p[v.v][t]=newdis;
            c.push({v.v,newdis});
        }
    }
}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//freopen("GH.INP","r",stdin);
	//freopen("GH.OUT","w",stdout);
	cin>>n>>m>>k;
	for (int i=1;i<=m;i++){
        int u,v;
        long long w;
        cin>>u>>v>>w;
        a[u].push_back({v,w});
        a[v].push_back({u,w});
	}
	for (int i=1;i<=k;i++)cin>>b[i];
	long long ans=inf;
	for (int j=20;j>=0;j--){
        bit[0].clear();
        bit[1].clear();
        for (int i=1;i<=k;i++){
            bit[(i>>j&1)].push_back(b[i]);
        }
        //cout<<bit[0].size()<<" "<<bit[1].size()<<'\n';
        sp(j);
        for (auto v:bit[1]){
            if (d[v][j].first<ans&&d[v][j].second!=0){
                ans=d[v][j].first;
                x=d[v][j].second,y=v;
            }
        }
        swap(bit[0],bit[1]);
        sp(j);
        for (auto v:bit[1]){
            if (d[v][j].first<ans&&d[v][j].second!=0){
                ans=d[v][j].first;
                x=d[v][j].second,y=v;
            }
        }
	}
	fix=x,fiy=y;
	for (int i=1;i<=n;i++){
        for (int j=20;j>=0;j--){
            d[i][j]={0,0};
        }
	}
	for (int j=20;j>=0;j--){
        bit[0].clear();
        bit[1].clear();
        for (int i=1;i<=k;i++){
            if (b[i]!=fix&&b[i]!=fiy)bit[(i>>j&1)].push_back(b[i]);
        }
        sp(j);
        for (auto v:bit[1]){
            if (d[v][j].first<another&&d[v][j].second!=0){
                another=min(another,d[v][j].first);
            }
        }
        swap(bit[0],bit[1]);
        sp(j);
        for (auto v:bit[1]){
            if (d[v][j].first<another&&d[v][j].second!=0){
                another=min(another,d[v][j].first);
            }
        }
	}
	long long dd=ans+another;
	anothersp(x,0);
	anothersp(y,1);
	prefix[0]=inf;
	p[x][0]=p[x][1]=p[y][0]=p[y][1]=inf;
	for (int i=1;i<=k;i++){
        prefix[i]=min(prefix[i-1],p[b[i]][1]);
	}
	suffix[k+1]=inf;
	for (int i=k;i>=1;i--){
        suffix[i]=min(suffix[i+1],p[b[i]][1]);
	}
	for (int i=1;i<=k;i++){
        long long value=p[b[i]][0]+min(prefix[i-1],suffix[i+1]);
        dd=min(dd,value);
	}
	cout<<dd;

}

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 0 / 25
• Subtask 4: 0 / 58