[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