首页 > 其他分享 >[ABC271E] Subsequence Path 题解

[ABC271E] Subsequence Path 题解

时间:2024-01-03 18:22:05浏览次数:33  
标签:int 题解 ll Subsequence ABC271E Path

[ABC271E] Subsequence Path 题解

思路解析

很好的一道题,很有迷惑性,表面上是一道图论实际上是 dp,定义 \(f_{i}\) 为从 \(1\) 到 \(i\) 的最短 “好路”。先把每条边对应的起点,终点和边权记录下来,然后输入每个 \(e\),由于是子序列顺序不会改变,因此可以顺序进行操作。对于每一个 \(e\),都有选和不选两种情况,若选,则相当于最短路算法中的松弛操作,转移 \(f_{a_{e}}\gets\min(f_{a_{e}},f_{b_{e}}+c_{e})\)(\(a_{i},b_{i},c_{i}\) 分别代表第 \(i\) 条边的起点,终点和边权)。

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
ll n, m, k;
ll a[N], b[N], c[N];
ll e;
ll f[N];
int main() {
	cin >> n >> m >> k;
	for(int i = 1; i <= m; i++) {
		cin >> a[i] >> b[i] >> c[i];
	}
	memset(f, 0x3f, sizeof(f));
	f[1] = 0;
	for(int i = 1; i <= k; i++) {
		cin >> e;
		f[b[e]] = min(f[b[e]], f[a[e]] + c[e]);
	}
	if(f[n] < 1e18) {
		cout << f[n];
	}
	else {
		cout << -1;
	}
	return 0;
}

标签:int,题解,ll,Subsequence,ABC271E,Path
From: https://www.cnblogs.com/2020luke/p/17943761

相关文章

  • P2726 [SHOI2005] 树的双中心 题解
    Description\(n\leq5\times10^4\),树的深度\(\leq100\)。Solution对于每个\(x,y\),满足\(d(v,x)\leqd(v,y)\)或者\(d(v,x)\geqd(v,y)\)的点一定构成一个子树,所以可以枚举这个子树的根,然后对两边分别求重心可以得到答案。但是直接暴力求是\(O(n^2)\)的,过不了。注......
  • CF763E Timofey and our friends animals题解
    题目链接:CF或者洛谷简单来说就是求\([l,r]\)这些点都存在的情况下,连通块的数量,看到七秒时限,而且每个点相连的边数很少,可以想到离线下来使用莫队类的算法解决连通块问题,一般可以考虑使用并查集解决。对于并查集来说,它的增加是非常简单的,但删除是困难的,可持久化并查集时空常数......
  • TinyMCE富文本编辑器粘贴图片自动上传问题解决
    TinyMCE编辑器支持粘贴图片,但是自动会将图片转换成base64编码,这样将内容提交到后台,数据会很大。  图|TinyMCE本文内容配置TinyMCE(版本:5.10.0)向编辑器中粘贴图片自动上传到后台,以下为配置代码:tinymce.init({selector:'#textarea',plugins:'previewautolinkdire......
  • 2023NCTFcheck题解-关于可视化shellcode以及AE64真香
    以后我会尽量少用图片,因为我经常在翻别人博客时发现图片加载不出来,很烦。看看checksec再看看IDAint__cdeclmain(intargc,constchar**argv,constchar**envp){__int64v3;//rbx__int64v4;//rbx__int64v5;//rbxunsigned__int64v7;//[rsp+8h][rbp-2......
  • P9753 [CSP-S 2023] 消消乐 题解
    这里是被说烂了的随机化线性做法。相信大家都已经做过QOJ6504,因此我们考虑采用类似的办法通过此题。我们对每个字符随机一个\(k\timesk\)的矩阵,并求出其矩阵的逆。然后,我们在偶数位放原矩阵,在奇数位放逆矩阵,这样,一段区间合法当且仅当这段区间的矩阵积为单位矩阵\(I\),原因......
  • CSP-S 题解
    非考场上想出来的会标星号。T1密码锁鲜花:我看到这道题的时候满脑子想的都是春测的lock。考虑到只有五个拨圈,每个拨圈只有\(10\)个状态,\(n\le8\),那么直接暴力枚举每个状态即可。考场代码://15:00//15:24.#include<bits/stdc++.h>usingnamespacestd;constin......
  • CF1748F 题解
    这3000?以下,\(\operatorname{op}(i)\)代表对\(i\)进行一次操作。我们考虑暴力。因为每一位都是分开处理的,我们考虑仅仅把一段区间的端点交换。即我们希望通过\(\operatorname{solve(l,r)}\)把\(a_ia_j\)交换而其他下标不动。一个显然的想法是,我们一定需要大量的前后缀异......
  • CF1844G 题解
    鉴定为学MO学的。MO中著名的《数学奥林匹克小丛书高中卷》的第十五本曾经讲过,如果原方程较难解,可以考虑给左右两边同时对\(M\)取模,然后研究取模以后的问题,其中\(M\)为一个根据问题选取的适当的整数。我们看见这个问题觉得很烦,因为大家都能发现这个条件给的相当于\(d_i+d......
  • P4894 题解
    实际上,这是两个向量的叉积已经是其他题解说烂了的。这里只是给出一个容易记忆\(dim\le3\)的行列式的值的办法。我们以\(3\)维行列式为例子,假设为\[\begin{vmatrix}a&b&c\\i&j&k\\o&p&q\end{vmatrix}\]我们有一个神奇的方法来记忆这个行列式的求值。首......
  • AT_arc127_a 题解
    在HL群里吃瓜,顺手写一篇题解。第一眼必定是数位dp,可是这会使原题难度反而升高了。相对而言,我们要是枚举前缀\(1\)的长度,然后寻找对答案有贡献的区间,此问题是很容易的。同时我们不难发现,前缀\(1\)长度为\(l\)的所有有贡献的数字即为\(\foralli\in[l,16],(\sum_{i=0}^l1......