【DP】ABC271 E - Subsequence Path

客官°小女子只卖身不卖艺 2024-03-23 11:21 52阅读 0赞

[E - Subsequence Path (atcoder.jp)][E - Subsequence Path _atcoder.jp]

题意：

给定一个路径序列，请问1-n的路径中，该路径是给定路径序列的子序列的最小值是多少。

![b0dfba188c51408dbca13761d2c02e1f.png][]

思路：

对于E这个路径序列中的每一条边，都有选和不选两种选择，那么可以递推一下，考虑选与不选两种决策更新最短路即可

Code：

#include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int Inf=1e18;
    struct ty{
        int u,v,w;
    }e[mxe<<2];
    
    int n,m,k,u,v,w;
    int dis[mxn],a[mxn];
    void solve(){
        cin>>n>>m>>k;
        for(int i=1;i<=m;i++){
            cin>>u>>v>>w;
            e[i]={u,v,w};
        }
        for(int i=1;i<=k;i++) cin>>a[i];
        for(int i=0;i<=n;i++) dis[i]=Inf;
        dis[1]=0;
        for(int i=1;i<=k;i++){
            int x=a[i];
            int b=e[x].v,a=e[x].u,w=e[x].w;
            dis[b]=min(dis[b],dis[a]+w);
        }
        if(dis[n]>=Inf) cout<<-1<<'\n';
        else cout<<dis[n]<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[E - Subsequence Path _atcoder.jp]: https://atcoder.jp/contests/abc271/tasks/abc271_e
[b0dfba188c51408dbca13761d2c02e1f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/cf1ab616f3b446bb9131229cedcd0bab.png

发表评论取消回复

表情：

评论列表（有 0 条评论，52人围观）

还没有评论，来说两句吧...

相关阅读

相关【DP】ABC271 E - Subsequence Path

[E - Subsequence Path (atcoder.jp)][E - Subsequence Path _atcoder.jp] 题意：给定一个路径序列，请问1

客官°小女子只卖身不卖艺/ 2024年03月23日 11:21/ 0 赞/ 53 阅读

相关 The path ‘E:\ZERO‘ does not belong to a directory.

<table> <thead> <tr> <th><font>问题描述</font></th> </tr> </thead> <tbody></

约定不等于承诺〃/ 2023年10月02日 17:21/ 0 赞/ 20 阅读

相关 271-Redis缓存穿透和雪崩

Redis缓存穿透和雪崩 Redis缓存的使用，极大的提高了应用程序的性能和效率，特别是数据查询等。但同时，它也带来了一些问题。其中，最主要的问题就是数据一致性，从严格意

左手的ㄟ右手/ 2022年11月19日 06:27/ 0 赞/ 89 阅读

相关 LeetCode-Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S. A

╰+哭是因爲堅強的太久メ/ 2022年08月04日 12:56/ 0 赞/ 127 阅读

相关 Subsequence

Subsequence Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Ja

一时失言乱红尘/ 2022年08月03日 05:15/ 0 赞/ 39 阅读

相关 Longest Ordered Subsequence

Longest Ordered Subsequence <table> <tbody> <tr> <td><strong>Time Limit:</stro

喜欢ヅ旅行/ 2022年07月16日 02:17/ 0 赞/ 168 阅读

相关 Common Subsequence ————LCS

A subsequence of a given sequence is the given sequence with some elements (possible non

亦凉/ 2022年05月17日 10:10/ 0 赞/ 160 阅读

相关 376. Wiggle Subsequence

A sequence of numbers is called a wiggle sequence if the differences between successive

缺乏、安全感/ 2022年04月23日 09:04/ 0 赞/ 148 阅读

相关 Common Subsequence

Description A subsequence of a given sequence is the given sequence with some element

╰半橙微兮°/ 2022年04月13日 14:40/ 0 赞/ 173 阅读

相关 subsequence 1(dp)

题目链接： [https://ac.nowcoder.com/acm/contest/885/G?&headNav=acm][https_ac.nowcoder.com_a

男娘i/ 2021年11月10日 05:06/ 0 赞/ 218 阅读