2025-ICPC-Asia-Taiwan-Online-台湾网络赛-C. One-Way Abyss（注意题目中的必须移动） · znzryb
## 题目大意
Mitty是一位勇敢的冒险者，正在探索一个被称为深渊的神秘地下洞穴系统。深渊由$n$个平行垂直井和$m$个水平隧道组成。每条隧道恰好连接两个相同深度的井。所有$m$个隧道的深度各不相同，令人惊讶的是，每条隧道的中间都藏有一宝藏！
Mitty可以选择任意一个井开始。他从所选井的顶部向下移动，遵守以下规则：
- **他只能向下移动，不允许向上移动。**
- **每当他遇到水平隧道时，必须立即进入，并将到达连接的井。**
- **一旦他进入水平隧道，就不能回头。**
这些隧道中的宝藏有各种价值。Mitty想要尽可能多地收集宝藏。请帮助他计算从一个井开始时他可以收集到的最大总宝藏价值。
最大样例的示例图：
## 思路讲解
可以把两个值绑在一起，当然三个，四个也是可以的。
注意，由于必须移动，因此不能够去 max。
```cpp
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](https://codeforces.com/gym/106084/submission/361088193)
::: 源代码
```cpp
/**
* 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……）