题目描述

翻译：有一系列节点，如 a,b,c ; 有 a * b –> c
完成c，需要完成a,b，同时杂交（a*b）过程的代价为 max（单独 a ，单独 b）

思路

本题的核心在于如何构建图：

相当于 add（a,c）中需要多存一个经过的节点b
或者 e[a]={b,c} 即 这条边 a 到 c 需经过 b

代价变更：

dis[ c ]=【max( dis[ a ] , dis[ b ] ) + 单独事件 max( ti[ a ] + ti[ b ] )】 与 【原本值】的最小值

C++ 代码

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int N=2e5+10;
vector<vector<PII>>edge(N);
vector<int>dis;
vector<int>ti;
vector<bool>vis;

void spfa()
{
    priority_queue<PII,vector<PII>,greater<PII>>q;

    q.push({0,0});
    while(!q.empty())
    {
        PII m=q.top();
        q.pop();

        int cur=m.second, dd=m.first;
        if(vis[cur])    continue;
        vis[cur]=true;

        for(auto e:edge[cur])
        {
            //cout<<dd<<"  "<<e.first<<"  "<<e.second<<'\n';
            if( dis[e.second] > ( max(dd,dis[e.first]) + max(ti[cur],ti[e.first]) ))
            {
                dis[e.second] = max(dd,dis[e.first]) + max(ti[cur],ti[e.first]);
                //<<"PU\n";
                //cout<<e.second<<"  "<<dis[e.second]<<'\n';
                q.push({dis[e.second],e.second});
            }
            //cout<<"----------------\n";
        }
    }
}

int main()
{
    int n,m,k,t;
    cin>>n>>m>>k>>t;
    dis.assign(n+1,0x3f3f3f3f);
    ti.resize(n+1);
    vis.resize(n+1,false);

    for(int i=1;i<=n;++i)
        cin>>ti[i];

    ti[0]=0;
    dis[0]=0;
    for(int i=0;i<m;++i)
    {
        int a;
        cin>>a;
        //dis[a]=0;
        edge[0].push_back({0,a});
    }

    for(int i=0;i<k;++i)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edge[a].push_back({b,c});
        edge[b].push_back({a,c});
    }
    spfa();
    cout<<dis[t];

}