某人看见没有题解表示不满给个参考

解题思路:

注意事项:

参考代码:

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1000010;

int e[N],ne[N],h[N],w[N],g[N],l[N],a,b,c,d,n,m,idx,ans,x,y,z;

void add(int a,int b,int c)

{

    l[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;

}

int dfs(int t)

{

    if(g[t]!=0x3f3f3f3f)

    {

        return g[t];

    }

    for(int i=h[t];~i;i=ne[i])

    {

        g[t]=min(g[t],max(dfs(e[i]),dfs(l[i]))+max(w[l[i]],w[e[i]]));

    }

    return g[t];

}

int main()

{

    cin>>a>>b>>c>>d;

    memset(h,-1,sizeof h);

    for(int i=1;i<=a;i++)

    {

        cin>>w[i];

        g[i]=0x3f3f3f3f;

    }

    for(int i=1;i<=b;i++)

    {

        cin>>x;

        g[x]=0;

    }

    for(int i=1;i<=c;i++)

    {

        cin>>x>>y>>z;

        add(z,x,y);

    }

    ans=dfs(d);

    cout<<ans<<endl;

    return 0;

}