题目链接
题解Dijkstra算法应用。(感觉好难,但是能看出来是用Dijkstra)
这道题要将每类种子视为一个节点,如果两类种子可以杂交,那么在两类种子上连边,将两类种子杂交生成的新种子的类别和新种子生成所需时间打包成一个pair视为边权,d[i]
表示由初始状态(即初始拥有若干类别的种子)到获取第i
类种子所需要的时间,最后答案输出的就是d[T]
。
最开始拥有的种子对应的d
都是0,表示经过0时间就可以获取到这些类别的种子,也就是初始状态。
同时我们还需要开辟一个have
数组,have[i]
表示我们是否找到了杂交得到第i
类种子的最优方案(即所需时间最短)。详细来说,我们可能在计算的时候算出一种获取到第i
类种子的杂交方式,但该方式可能不是最佳的,那么我们就还不能将have[i]
设置为1,只有当我们确定了这个方案是最佳的时候,才能将have[i]
标记为1。 显然,初始状态的种子对应的have
均为1。
这样就处理完了初始种子的相关信息。
接下来处理种子杂交谱。
对于输入的杂交谱,每个三元组,都可以构造出一条边,前两个数为两个祖先节点,最后一个数是边权中的一项,另一项是生成孩子节点所需的时间,也即两个祖先节点生长所需时间的最大值,也就是孩子节点生成所需的时间(只不过这个时间并不一定是最短的,所以不会对have
进行设置)。
如果两个祖先(父亲)种子我们可以直接得到,也就是说两个祖先种子都是初始状态中的种子,那么我们将二者杂交得到的孩子种子的类型和种子生成所需要的时间打包成一个pair,将这个pair加入到优先队列中。当然第一维应该是时间,保证队列中时间少在队头。同时,如果两个祖先种子都是初始状态中的种子,那么我们可以先更新一下二者孩子节点对应的d
,尽管不一定是最终的结果,但是最起码现在我们找到了一种方案得到孩子节点对应的种子类别,所以先更新一下。
对优先队列进行操作。
优先队列中保存的是边权,上面也说了,边权就是由种子类别和此类别种子生成的时间构成的pair。(这么一看又不像边权了,反而像是一个节点带着一个自己生成所需时间的信息。这道题奇怪就奇怪在这,边又是点,点又是边,所以好难啊)
剩下的部分看代码注释吧!
代码#include
#define x first
#define y second
#define PII pair
using namespace std;
const int N = 2010, M = 2e5+10; // 边要开到 M !
priority_queue q;
int target[M], cost[M], e[M], ne[M], h[N], idx;
int g[N], d[N], have[N];
void add (int u, int v, int k, int t) {
target[idx] = k, cost[idx] = t, e[idx] = v, ne[idx] = h[u], h[u] = idx ++;
// target[i]表示索引为i的边对应的两个节点生成的孩子
// cost[i]表示索引为i的边对应的两个节点生成的孩子所需要的时间
}
int getgrowthtime (int a, int b) {
return max (g[a], g[b]);
}
int main()
{
memset (h, -1, sizeof h);
memset (d, 0x3f, sizeof d);
int N, M, K, T;
cin >> N >> M >> K >> T;
for (int i = 1;i > g[i]; // 记录每种种子的生长时间
while (M --) {
int kind;
cin >> kind;
have[kind] = 1;
d[kind] = 0;
}
while (K --) {
int u, v, kd;
cin >> u >> v >> kd;
int t = max (g[u], g[v]);
if (have[u] && have[v] && t gt + c) // have[kd2]==1(已经确定得到kd2的最好方案了),have[tar]==0(没确定得到tar的最好方案所以才要更新d[tar]),d[tar] > gt + c(已经记录的得到tar的方案花费大于通过kd1和kd2生成tar的花费)
d[tar] = gt + c, // 更新
q.push ({d[tar], tar}); // 入队
}
}
// for (int i = 1;i
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?