[ABC271E] Subsequence Path Solution

更好的阅读体验戳此进入

题面

给定 $n$$n$ 个点 $m$$m$ 条边有边权无自环的无向图，给定边集序列 $E_k$$E_k$，求边集序列的子序列路径使得能按序从 $1$$1$ 到 $n$$n$ 且路径长度最小，输出最小值，无解输出 -1。

Solution

最开始的思路是把边集下放然后每个点挂多个 pair < ll, int > 表示到这个点的所有可能的权值与其对应的最小的序列终止位置，然后用类似二维偏序的思路转移，但是不确定这个思路假没假以及复杂度是否正确，不过细想一下就会发现这题实际上特别水。

不难发现我们要找的是边的子序列，也就是其是有顺序的，那么我们直接按照边序列顺序跑的话显然是无后效性的，所以我们可以按照最短路的思想，考虑记录到每个点的 $dis$$dis$，然后按序列顺序遍历边，用其起始点的 $dis$$dis$ 加上边权去更新该点的 $dis$$dis$，注意到这里我们可以这么做的原因是如果要求前面的边，一定不会在其之前先走后面的边，这也就是我们刚才提到的无后效性，这样最后 $di{s}_n$$dis_n$ 就是答案了。

Code

xxxxxxxxxx
59
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define INFLL (0x3f3f3f3f3f3f3f3fll)
24

25
template < typename T = int >
26
inline T read(void);
27

28
int N, M, K;
29
struct{int s, t, v;}edg[210000];
30
ll dis[210000];
31

32
int main(){
33
    memset(dis, 0x3f, sizeof dis);
34
    N = read(), M = read(), K = read();
35
    for(int i = 1; i <= M; ++i)edg[i].s = read(), edg[i].t = read(), edg[i].v = read();
36
    dis[1] = 0;
37
    for(int i = 1; i <= K; ++i){
38
        int idx = read();
39
        dis[edg[idx].t] = min(dis[edg[idx].t], dis[edg[idx].s] + edg[idx].v);
40
    }printf("%lld\n", dis[N] == INFLL ? -1ll : dis[N]);
41
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
42
    return 0;
43
}
44

45
template < typename T >
46
inline T read(void){
47
    T ret(0);
48
    int flag(1);
49
    char c = getchar();
50
    while(c != '-' && !isdigit(c))c = getchar();
51
    if(c == '-')flag = -1, c = getchar();
52
    while(isdigit(c)){
53
        ret *= 10;
54
        ret += int(c - '0');
55
        c = getchar();
56
    }
57
    ret *= flag;
58
    return ret;
59
}

UPD

update-2023_02_09 初稿。

update-2023_02_09 审核说的问题是 “句子末尾应加句末句号（全角）”，我实在是没找到哪里缺句号了，只能在 “初稿” 这个非句子的词语后加了个句号。