Submission #1175456

#TimeUsernameProblemLanguageResultExecution timeMemory
1175456WarinchaiRelay Marathon (NOI20_relaymarathon)C++20
25 / 100
3958 ms262804 KiB
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>adj[100005];
pair<int,int> dis[100005][2];
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=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};
    }
    for(int i=0;i<=n;i++)dis[i][0]=dis[i][1]={inf,inf};
    while(!pq.empty()){
        int d=pq.top().dis;
        int x=pq.top().cur;
        int r=pq.top().root;
        pq.pop();
        if(d<dis[x][0].first)dis[x][1]=dis[x][0],dis[x][0]={d,r};
        else if(d<dis[x][1].first&&r!=dis[x][0].second)dis[x][1]={d,r};
        else continue;
        for(auto v:adj[x]){
            pq.push({state(r,d+v.second,v.first)});
        }
    }
    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++){
        int val=dis[i][0].first+dis[i][1].first;
        int x=dis[i][0].second;
        int y=dis[i][1].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]));
        }
    }
    cout<<(rans==inf?-1:rans);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...