Submission #976549

#	Time	Username	Problem	Language	Result	Execution time	Memory
976549		Haanhtien	Relay Marathon (NOI20_relaymarathon)	C++14	17 / 100	242 ms	49104 KiB

RelayMarathon

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
const ll N=1e5+10;
const ll M=4e5+10;
ll n,m,k;
ll d[N],flag[N],h[N];
ll mark[N],a[N];
struct edge {
    long long u,v,w;
};
edge c[M];
vector<pair<ll,ll>> g[N];
void Dis(){
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
    for(long long i=1;i<=n;i++)
        if(d[i]==0) pq.push({0,i});
    while(!pq.empty()){
        ll val=pq.top().fi,u=pq.top().se; pq.pop();
        if(d[u]!=val) continue; 
        for(auto e:g[u]){
            long long w=e.se,v=e.fi;
            if(d[v]==d[u]+w) flag[v]=1;
            if(d[v]>d[u]+w)
            {
                h[v]=h[u],d[v]=d[u]+w,flag[v]=0;
                pq.push({d[v],v});
            }
        }
    }
}
int main ()
{
    //freopen("cities.inp","r",stdin);
    //freopen("cities.out","w",stdout); 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>k;
    fill(d+1,d+n+1,1e18);
    for(ll i=1;i<=m;i++)
    {
        ll u,v,w;
        cin>>u>>v>>w;
        c[i].u=u;
        c[i].v=v;
        c[i].w=w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    for(long long i=1;i<=k;i++)
    {
        long long x;
        cin>>x;
        d[x]=flag[x]=0;
        h[x]=x;
    }
    Dis();
    long long a_main=0,b_main=0,t=1e18;
    for(long long i=1;i<=m;i++)
    {
        long long u=c[i].u,v=c[i].v,w=c[i].w;
        if(d[u]<1e18 && d[v]<1e18)
        {
            if(flag[u]==1 || flag[v]==1 || h[u]!=h[v])
            {
                long long t_try=d[u]+d[v]+w;
                if(t_try<t)
                {
                    a_main=h[u];
                    b_main=h[v];
                    t=t_try;
                }
            }
        }
    }
    //cout<<t<<'\n';
    long long t2=1e18,abest1=1e18,abest2=1e18,bbest1=1e18,bbest2=1e18,a1=1e18,b1=1e18;
    for(long long i=1;i<=m;i++)
    {
        long long u=c[i].u,v=c[i].v,w=c[i].w;
        if(d[u]<1e18 && d[v]<1e18)
        {
            if(flag[u]==1 || flag[v]==1 || h[u]!=h[v])
            {
                long long t_try=d[u]+d[v]+w;
                //cout<<u<<" "<<v<<" "<<h[u]<<" w "<<h[v]<<'\n';
                if(h[u]!=a_main && h[v]!=a_main && h[u]!=b_main && h[v]!=b_main && t_try<t2)
                {
                    t2=t_try;
                    continue;
                }
                if((h[u]==a_main && h[v]!=b_main) || (h[v]==a_main && h[u]!=b_main))
                {
                    if(t_try<abest1)
                    {
                        abest2=abest1;
                        abest1=t_try;
                        a1=(h[u]==a_main ? h[v]:h[u]);
                    }
                    else if(t_try<abest2)
                        abest2=t_try;
                }
                if((h[u]!=a_main && h[v]==b_main) || (h[v]!=a_main && h[u]==b_main))
                {
                    if(t_try<bbest1)
                    {
                        bbest2=bbest1;
                        bbest1=t_try;
                        b1=(h[u]==b_main ? h[v]:h[u]);
                    }
                    else if(t_try<bbest2) bbest2=t_try;
                }
            }
        }
    }
    long long dmin=t+t2;
    //cout<<t2<<'\n';
    if(a1==b1) dmin=min({dmin,abest1+bbest2,abest2+bbest1});
    else dmin=min(dmin,abest1+bbest1);
    cout<<dmin;
    return 0;
}

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