2025-ICPC-Asia-Taiwan-Online-台湾网络赛-C. One-Way Abyss（注意题目中的必须移动）

题目大意

Mitty是一位勇敢的冒险者，正在探索一个被称为深渊的神秘地下洞穴系统。深渊由$n$个平行垂直井和$m$个水平隧道组成。每条隧道恰好连接两个相同深度的井。所有$m$个隧道的深度各不相同，令人惊讶的是，每条隧道的中间都藏有一宝藏！

Mitty可以选择任意一个井开始。他从所选井的顶部向下移动，遵守以下规则：

• 他只能向下移动，不允许向上移动。

• 每当他遇到水平隧道时，必须立即进入，并将到达连接的井。

• 一旦他进入水平隧道，就不能回头。

这些隧道中的宝藏有各种价值。Mitty想要尽可能多地收集宝藏。请帮助他计算从一个井开始时他可以收集到的最大总宝藏价值。

最大样例的示例图：

思路讲解

可以把两个值绑在一起，当然三个，四个也是可以的。

注意，由于必须移动，因此不能够去 max。

void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<ll> dp(N+2);
    for (int i=1;i<=M;++i) {
        ll u,v,w;
        cin>>u>>v>>w;
        tie(dp[u],dp[v])=(pair<ll,ll>){dp[v]+w,dp[u]+w};
    }
    ll ans=*max_element(all(dp));
    cout<<ans<<"\n";
}

AC代码

AC
https://codeforces.com/gym/106084/submission/361088193

源代码

/**
 * Problem: C. One-Way Abyss
 * Contest: 2025 ICPC Asia Taiwan Online Programming Contest
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106084/problem/C
 * Created: 2026-02-02 13:59:00
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<ll> dp(N+2);
    for (int i=1;i<=M;++i) {
        ll u,v,w;
        cin>>u>>v>>w;
        tie(dp[u],dp[v])=(pair<ll,ll>){dp[v]+w,dp[u]+w};
    }
    ll ans=*max_element(all(dp));
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106084/submission/361088193

*/

心路历程（WA，TLE，MLE……）