CF-1029-G. Omg Graph（路径成本定义为最短边和最长边之和） · znzryb
## 思路讲解
注意到呢，把边固定下来，然后这个时候就只要去看简单路径了。因为走越多，遇到大的边的可能性越大。
当然，我们的下一步推进遇到了问题，这个问题不是树上问题，m 没有限定，那么 dp 就废了。
不过问题不大，容易想到如果不是树，我们能不能把它变为树？用最小生成树。
## AC代码
AC
[https://codeforces.com/contest/2117/submission/323773579](https://codeforces.com/contest/2117/submission/323773579)
::: 源代码
```cpp
// Problem: G. Omg Graph
// Contest: Codeforces - Codeforces Round 1029 (Div. 3)Codeforces 第 1029 轮（第 3 组）
// URL: https://codeforces.com/contest/2117/problem/G
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
ll N,M,Q,X,K,lT,A[MAXN];
/*
*/
vector<arr2> g[MAXN]; // 最小生成树
bitset<MAXN> vis;
inline void init(){
FOR(i,0,N+5){g[i].clear();vis[i]=false;}
}
struct DSU { // 并查集
vector<int> fa, siz;
int ln;
DSU(int n) {
ln = n;
fa.resize(ln + 5, 0), siz.resize(ln + 5, 0);
FOR(i, 1, n) {
fa[i] = i;
siz[i] = 1;
}
}
int find(int x) {
while (fa[x] != x) {
x = fa[x];
fa[x] = fa[fa[x]];
}
return x;
}
bool same(int x, int y) { return find(x) == find(y); }
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
fa[y] = x;
return true;
}
int size(int x) { return siz[find(x)]; }
int countFa() {
int res = 0;
FOR(i, 1, ln) {
if (fa[i] == i) ++res;
}
return res;
}
};
ll mxW[MAXN][2],mnW[MAXN][2];
void dfs(ll node,ll wei,ll ci){
vis[node]=true;
mxW[node][ci]=wei;
FOR(i,0,SZ(g[node])-1){
ll lnode=g[node][i][0],w=g[node][i][1];
if(vis[lnode]) continue;
dfs(lnode,max(wei,w),ci);
}
}
void dfsn(ll node,ll wei,ll ci){
vis[node]=true;
mnW[node][ci]=wei;
FOR(i,0,SZ(g[node])-1){
ll lnode=g[node][i][0],w=g[node][i][1];
if(vis[lnode]) continue;
dfsn(lnode,min(wei,w),ci);
}
}
arr3 edge[MAXN];
inline void solve(){
cin>>N>>M;
init();
priority_queue<arr3,vector<arr3>,greater<arr3> > pq;
FOR(i,1,M){
ll u,v,w;
cin>>u>>v>>w;
pq.push({w,u,v});
edge[i]={u,v,w};
}
DSU fa(N);
// ll mnw=pq.top()[0];
vector<arr2> wp; // wait processing
while(!pq.empty()){ // kruskal
arr3 t=pq.top();pq.pop();
ll w=t[0],u=t[1],v=t[2];
// if(w==mnw) wp.pb({u,v});
if(!fa.same(u,v)){
fa.merge(u,v);
g[u].pb({v,w});
g[v].pb({u,w});
}
}
dfs(1,0,0);
FOR(i,0,N+5) vis[i]=false;
dfs(N,0,1);
FOR(i,0,N+5) vis[i]=false;
dfsn(1,INF,0);
FOR(i,0,N+5) vis[i]=false;
dfsn(N,INF,1);
ll ans=INF;
mnW[1][0]=0,mnW[N][1]=0;
#ifdef LOCAL
FOR(i,1,N){
debug(i);
debug(mxW[i][0]);
debug(mxW[i][1]);
}
FOR(i,1,N){
debug(i);
debug(mnW[i][0]);
debug(mnW[i][1]);
}
#endif
FOR(i,1,M){
ll u=edge[i][0],v=edge[i][1],w=edge[i][2];
ll lans=INF,lans2=INF;
lans=min(lans,max({mxW[u][0],mxW[v][1],w}));
lans=min(lans,max({mxW[v][0],mxW[u][1],w}));
lans2=min(lans2,min(mnW[u][0],mnW[v][1]));
lans2=min(lans2,min(mnW[v][0],mnW[u][1]));
lans2=max(lans2,edge[i][2]);
ans=min(ans,lans+lans2);
#ifdef LOCAL
debug(u);
debug(v);
debug(ans);
debug(lans);
debug(lans2);
debug(mxW[u][0]);
cerr<<"\n";
#endif
}
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--){
solve();
}
// solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2117/submission/323773579
*/
```
:::
## 心路历程（WA，TLE，MLE……）