上图来源于Kazimierz
思路
由于题目中给出了已有的作物和目标作物,我们要使用这些作物和杂交方案来得到目标作物,并且所需时间最短。如上图所示,现在有两种作物a,b,a和b杂交可以生成c,因此在a和c之间构造一条边:a–>c,边权存储所需的杂交时间和与a进行杂交的另一种作物b;再构造另外一条边:b–>c,边权存储所需的杂交时间和与b进行杂交的另一种作物a(无向边),这样就将作物杂交问题抽象成图的问题。
由于c是由a和b杂交而成的,w为杂交得到c的时间,而a和b都是通过杂交得到的,各自所需的时间可能是不一样的,因此两者要取最大值,然后加上w,即为杂交得到c的时间,然而使用其他植物通过杂交也能得到植物c,与上述同理,最后取最小值,因此求得了杂交得到c的最短时间,更新杂交时间的方式为:tim[j]=min(tim[j],max(tim[var],tim[g[i]])+w[i]), g[i]存储与var进行杂交的另一种作物的编号
dijkstra算法:
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
const int N=2010,M=2e5+10;//A×B与B×A得到的作物是一样的
typedef pair<int,int> PII;//第一个表示时间,第二个值表示作物的编号
int tim[N];//存储得到第i种作物需要杂交的时间
bool st[N];
int h[N],e[M],w[M],ne[M],g[M],idx;
int T[N];
priority_queue<PII,vector<PII>,greater<PII>> heap;//小根堆
void add(int a,int b,int c)//a和b杂交得到c
{
e[idx]=c;//存储杂交得到的作物编号
g[idx]=b;//g来存储与a杂交的另外一种作物b
w[idx]=max(T[a],T[b]);//a和b杂交所需时间为a和b的种植时间的最大值
ne[idx]=h[a];
h[a]=idx++;
}
void dijkstra()
{
while(heap.size())
{
auto t=heap.top();//堆顶为最小值
heap.pop();
int var=t.second;//当前作物的编号
if(st[var]) continue;
st[var]=true;
for(int i=h[var];i!=-1;i=ne[i])
{
int j=e[i];
if(tim[j]>max(tim[var],tim[g[i]])+w[i])
{
tim[j] = max(tim[var],tim[g[i]]) + w[i];
heap.push({tim[j],j});
}
}
}
}
int main()
{
int n,m,k,t;
cin>>n>>m>>k>>t;
for(int i=1;i<=n;i++)
cin>>T[i];
memset(tim,0x3f,sizeof tim);
while(m--)
{
int x;
cin>>x;
tim[x]=0;//编号为x的作物杂交前的时间为0
heap.push({0,x});//初始时,将当前拥有种子的编号放入堆中,时间为0
}
memset(h,-1,sizeof h);
while(k--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c),add(b,a,c);//与无向边类似
}
dijkstra();
cout<<tim[t];//输出得到目标作物的最短杂交时间
return 0;
}