原题链接

前言

这是一道非常有价值的题，因为他不同于一般的最短问题，不能直接套模板建图。本题相较于一般的最短路问题更能接近最短路的本质。本题的难点在于建图即如何将一个具体问题抽象成一个图的问题，它教会我们了一个很强的结论，即在构建图的过程中，边不仅可以存储边权，还可以存储其他额外信息！！！，这也为我们以后解决相关问题提供的很大的灵活空间。

分析

原题描述的是作物的杂交，已知一个关系的集合，这个集合描述了两种作物杂交如何得到另一种作物，花费的时间是两者生长的最大值。题目给定我们一个目标作物，和已有的作物，要我们通过已有的作物通过杂交关系生成目标作物，并且所花费的时间最短。

我们首先分析样例

我们根据样例所给出的数据构造出了一个有向图，假定有关系(a,b,c)，即a和b杂交可以生成c，我们就根据此关系构建两条边，第一条：a -> c，边权维护时间w以及节点b，第二条:b -> c，边权维护时间w以及节点a，当我们遍历到a的时候可以找到c，同样当我们遍历到b的时候也可以找到c，并且我们可以通过边权读取到与这个节点a关联的另一节点b，这样我们便完整描述了所有节点之间的关系，问题转化为了一个图的问题。

既然我们可以对数据构建有向图，答案是要求通过杂交得到t的最短时间，其实就是求通过已知作物达到节点t的最短路径。

由于已知作物不止一个，所以这并不是一个单源最短路径问题，我们需要对问题再作更近一步的转换。

这便用到了另一个神奇的知识，那便是超级源点！！！

我们构建一个虚拟的零号节点，并把这个节点指向已知的节点，边权设置为0，然后从这个节点开始搜索，这样一个多源单汇问题就转化为了一个单源单汇问题！！！

至此，最短路模型完全建立！

SPFA算法 时间复杂度：最坏情况$ O(nm) $ 平均情况$ O(m) $，$n$为点数，$m$为边数

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

const int N = 2050,K = 2e5 + N;
int h[N],ne[K],w[K],e[K],idx,g[K];
int n,m,k,tar,t[N],dis[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx] = c,w[idx] = max(t[a],t[b]),g[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

int spfa()
{
    memset(dis,0x3f,sizeof dis);
    queue<int> q;
    q.push(0);
    st[0] = true;
    dis[0] = 0;
    
    while(q.size())
    {
        int tmp = q.front();
        q.pop();
        st[tmp] = false;
        
        for(int i=h[tmp];~i;i=ne[i])
        {
            int ver = e[i];
            if(dis[ver] > max(dis[tmp],dis[g[i]]) + w[i])
            {
                dis[ver] = max(dis[tmp],dis[g[i]]) + w[i];
                if(!st[ver])
                {
                    q.push(ver);
                    st[ver] = true;
                }
            }
        }
    }
    return dis[tar];
}

int main()
{
    memset(h,-1,sizeof h);
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k>>tar;
    for(int i=1;i<=n;i++) cin>>t[i];
    for(int i=1;i<=m;i++)
    {
        int x;
        cin>>x;
        add(0,0,x);
    }
    
    while(k--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    cout<<spfa()<<endl;
    return 0;
}