Submission #1175494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175494		Warinchai	Relay Marathon (NOI20_relaymarathon)	C++20	25 / 100	1901 ms	103664 KiB

RelayMarathon

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>adj[100005];
vector<pair<int,int>>dis[100005];
map<int,int>has[100005];
vector<int>sp;
struct state{
    int root,dis,cur;
    state(int r,int d,int c){
        root=r,dis=d,cur=c;
    }
    friend bool operator<(state a,state b){
        return a.dis>b.dis;
    }
};
int inf=1e9;
priority_queue<state>pq;
int can(pair<int,pair<int,int>>ans1,pair<int,pair<int,int>>ans2){
    if(ans1.first==inf||ans2.first==inf)return inf;
    bool temp=(ans1.second.first!=ans2.second.first&&ans1.second.first!=ans2.second.second&&ans1.second.second!=ans2.second.first&&ans1.second.second!=ans2.second.second);
    if(temp)return ans1.first+ans2.first;
    else return inf;
}
map<pair<int,int>,int>mp;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m,k;cin>>n>>m>>k;
    for(int i=1;i<=n;i++)dis[i].resize(4,{inf,inf});
    for(int i=0;i<m;i++){
        int u,v,w;cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    for(int i=1;i<=k;i++){
        int x;cin>>x;
        sp.push_back(x);
        pq.push(state(x,0,x));
        dis[x][0]={0,x};
    }
    while(!pq.empty()){
        int d=pq.top().dis;
        int u=pq.top().cur;
        int r=pq.top().root;
        pq.pop();

        for(auto v:adj[u]){
            int x=v.first;

            if(d+v.second>=dis[x][3].first)continue;

            int temp=-1;
            for(int i=0;i<3;i++)if(dis[x][i].second==r)temp=i;
            if(temp!=-1)continue;

            dis[x].push_back({d+v.second,r});
            sort(dis[x].begin(),dis[x].end());
            temp=dis[x][4].second;
            dis[x].pop_back();
            if(temp==r)continue;
            pq.push({state(r,d+v.second,v.first)});
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<4;j++){
            if(dis[i][j].first==inf)break;
            for(int k=j+1;k<4;k++){
                assert(dis[i][j].second!=dis[i][k].second);
            }
        }
    }
    /*cerr<<"\n";
    for(int i=1;i<=n;i++){
        cerr<<"i:"<<i<<":"<<dis[i][0].first<<" "<<dis[i][1].first<<" "<<dis[i][2].first<<" "<<dis[i][3].first<<"\n";
    }*/
    int rans=inf;
    pair<int,pair<int,int>>ans[4];
    for(int i=0;i<4;i++){
        ans[i]={inf,{inf,inf}};
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<4;j++){
            for(int k=j+1;k<4;k++){
                if(dis[i][j].first==inf||dis[i][k].first==inf)continue;
                int val=dis[i][j].first+dis[i][k].first;
                int x=dis[i][j].second;
                int y=dis[i][k].second;
                if(x>y)swap(x,y);
                if(mp[{x,y}]==0||mp[{x,y}]>val)mp[{x,y}]=val;
            }
        }
    }
    for(auto x:mp){
        int val=x.second;
        int u=x.first.first;
        int v=x.first.second;
        if(val<ans[0].first){
            ans[3]=ans[2];
            ans[2]=ans[1];
            ans[1]=ans[0];
            ans[0]={val,{u,v}};
        }else if(val<ans[1].first){
            ans[3]=ans[2];
            ans[2]=ans[1];
            ans[1]={val,{u,v}};
        }else if(val<ans[2].first){
            ans[3]=ans[2];
            ans[2]={val,{u,v}};
        }else if(val<ans[3].first){
            ans[3]={val,{u,v}};
        }
    }
    for(int i=0;i<3;i++){
        for(int j=i+1;j<3;j++){
            rans=min(rans,can(ans[i],ans[j]));
        }
    }
    assert(rans>1);
    cout<<(rans==inf?-1:rans);
}

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