Submission #976524

#	Time	Username	Problem	Language	Result	Execution time	Memory
976524		phcbaka	Relay Marathon (NOI20_relaymarathon)	C++17	0 / 100	3 ms	14684 KiB

RelayMarathon

#include<bits/stdc++.h>
 
using namespace std;
#define N  100010
#define ll long long
#define ii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define iii pair<int,ii>
#define int ll
 
int n,m,k,ans=1e18,ktr[N],spec[N],check[N];
vector<ii>g[N];
ii dp[N][2];
priority_queue<ii>s;
iii b[N];
 
struct vet
{
    int ktr[510]={},a[510][510];
    ii dp[510][510];
 
    void xuli()
    {
        memset(a,0x3f3f,sizeof(a));
        for(int i=1;i<=n;i++)
            a[i][i]=0;
        for(int i=1;i<=m;i++)
        {
            int u,v,L;
            cin>>u>>v>>L;
            a[u][v]=min(a[u][v],L);
            a[v][u]=min(a[v][u],L);
        }
        for(int i=1;i<=k;i++)
        {
            int u;
            cin>>u;
            ktr[u]=1;
        }
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
      //  cout<<a[3][5]<<endl;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                if(ktr[i]==0||ktr[j]==0||(i==j))
                    dp[i][j]={1e9,j};
                        else dp[i][j]={a[i][j],j};
            sort(dp[i]+1,dp[i]+1+n);
        }
        int ans=1e18;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int t=1;t<=min(5ll,n);t++)
                    for(int c=1;c<=min(5ll,n);c++)
                        if(i!=j&&i!=dp[i][t].sc&&i!=dp[j][c].sc&&j!=dp[i][t].sc&&j!=dp[j][c].sc&&dp[i][t].sc!=dp[j][c].sc)
                        {
                            ans=min(ans,dp[i][t].fs+dp[j][c].fs);
                        }
        cout<<ans;
        exit(0);
    }
}vet;
 
void DFS(int u)
{
    ktr[u]=1;
    if(spec[u]==1)
    {
        dp[u][0]={0,u};
        s.push({0,u});
    }
    for(auto v:g[u])
        if(ktr[v.sc]==0)
        {
            DFS(v.sc);
        }
}
 
void dijkstra()
{
    while(!s.empty())
    {
        ii cc=s.top();
        int u=cc.sc,L=-cc.fs;
        s.pop();
        if(check[u])
            continue;
        check[u]=1;
        for(auto v:g[u])
        {
            if(dp[v.sc][0].fs>v.fs+L)
            {
                if(dp[v.sc][0].sc!=dp[u][0].sc)
                    dp[v.sc][1]=dp[v.sc][0];
                dp[v.sc][0]={v.fs+L,dp[u][0].sc};
                s.push({-dp[v.sc][0].fs,v.sc});
            }else
            {
                if(dp[v.sc][0].sc!=dp[u][0].sc&&dp[v.sc][1].fs>v.fs+L)
                {
                    dp[v.sc][1]={v.fs+L,dp[u][0].sc};
                }
            }
        }
    }
}
 
bool SS(const iii&a,const iii&b)
{
    return a.sc<b.sc;
}
 
int ST[N*4];
 
void update(int id,int l,int r,int i,int val)
{
    if(l>i||r<i)
        return;
    if(l==r)
    {
        ST[id]=min(ST[id],val);
        return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,i,val);
    update(id*2+1,mid+1,r,i,val);
    ST[id]=min(ST[id*2],ST[id*2+1]);
}
 
int get(int id,int l,int r,int u,int v)
{
    if(l>v||r<u)
        return 1e18;
    if(l>=u&&r<=v)
        return ST[id];
    int mid=(l+r)/2;
    return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
 
int32_t main()
{
   // freopen("4special.inp","r",stdin);
   // freopen("4special.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m>>k;
    if(n<=500&&m<=500)
        vet.xuli();
    
    return 0;
}

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