CF2117G + 23合肥区域赛J¶

created on 2025 08-02

这个 2117G 是有一段时间之前的 div 3 的题了，当时看就觉得不是很难，记得之前写过一个类似的题，虽然也是看题解了的。

但是昨晚再写这个2117G还是不会，看了题解才明白了。。。

CF2117G ¶

给一个无向图，定义路径的长度为经过的边中最大边与最小边的长度之和，求 \(1\) 到 \(n\) 的最小距离。

如果求 \(1\) 和 \(n\) 到每个点经过的最小的最大边或者是经过的最小的最小边是比较容易的，可以用 dijkstra，但如果想同时考虑这两个问题，不太容易做到。

并且如果你求 \(1\) 和 \(n\) 到每个点经过的最小的最小边，那么中途可能会经过大的边，不太好。那么如果我们求出来了 \(1\) 和 \(n\) 到每个点的最小的最大边的长度，又该怎么得到答案呢？

我就是不太能想得到这里，我想的是，你是不是可以尝试去走所有小于等于某个长度的边，然后看能走到的最小边是啥，但显然时间复杂度不太行。。。

看了题解才感觉，真妙啊，其实也挺简单。我们去枚举每一条边，对于 \(u, v, w\) 这条边，假如它是 \(1\) 到 \(n\) 中的一条边，那么要么是 \(1\) 走到 \(u\)，\(v\) 走到 \(n\)，要么就是反过来。所以只要我们枚举每一条边，一定可以枚举到 \(w\) 是答案中的最短边，再加上两端的最大距离就可以了。

好像其实没什么难的地方，这种题一定要考虑就是枚举每一条边作为路径的一部分。而且还是以前看过的原题，另一题真的基本一模一样。

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

void solve()
{
    // 基本上一模一样 https://codeforces.com/gym/104857/problem/J
    int n, m;
    cin >> n >> m;
    vector<vector<pii>> vec(n + 1);
    vector<array<int, 3>> edges;
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        vec[u].push_back({v, w});
        vec[v].push_back({u, w});
        edges.push_back({u, v, w});
    }
    /*
    如果可以知道只经过小于 w 的边可以到达的最短的边是多少，会比较方便
    因为如果只算某个点到 1 和  n 经过的最大边，是比较方便的，且不怎么影响小的边
    反之影响更大，不方便

    呃 是不是不用考虑那么多 求最短的最大边的时候 顺便记录经过的最小边是不是就行了
    */
    auto dijkstra = [&](int s) -> vector<int> {
        vector<int> dis(n + 1, 1e9);
        priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> pq;
        pq.push({0, s});
        while(pq.size()){
            auto [dist, u] = pq.top();
            pq.pop();
            if(dis[u] < dist) continue;
            for(auto [v, w] : vec[u]){
                if(max(w, dist) < dis[v]){
                    dis[v] = max(w, dist);
                    pq.push({dis[v], v});
                }
            }
        }
        return dis;
    };
    vector<int> dis1 = dijkstra(1);
    vector<int> disn = dijkstra(n);
    int ans = INT_MAX;
    for(auto [u, v, w] : edges){
        // cerr << format("u, v, w : [{}, {}, {}]\n", u, v, w);
        // cerr << format("dis1[u], disn[v] : {} {} dis1[v], disn[u] : {} {}\n", dis1[u], disn[v], dis1[v], disn[u]);
        ans = min(ans, min(max({dis1[u], disn[v], w}), max({dis1[v], disn[u], w})) + w);
    }
    cout << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}

这个题目还可以用 dsu 来做。因为是最大边加最小边，我们可以按边权排序，然后加边，若 \(1\) 和 \(n\) 联通，则一定可以经过该连通块中的最小边。

写了一下 dsu 写法，不过本来我是不太理解为什么可以 dsu，这个也是挺不错的。

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

void solve()
{
    // 基本上一模一样 https://codeforces.com/gym/104857/problem/J
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> edges;
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }
    vector<int> f(n + 1), mn(n + 1, 1e9);
    iota(f.begin() + 1, f.end(), 1);

    auto find = [&](auto &&self, int x) -> int{
        return f[x] == x ? x : f[x] = self(self, f[x]);
    };
    ranges::sort(edges, [](array<int, 3> x, array<int, 3> y){
        return x[2] < y[2];
    });
    int ans = 2e9;
    for(auto [u, v, w] : edges){
        int fu = find(find, u), fv = find(find, v);
        mn[fv] = min(mn[fv], w);
        mn[fu] = min(mn[fu], mn[fv]);
        f[fv] = fu;
        if(find(find, 1) == find(find, n)){
            ans = min(ans, mn[f[1]] + w);
        }
    }
    cout << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}

那么对于 dijkstra 的方法，其实我们本质只用枚举 \(w\) 作为路径中的最短边，因为我刚才看了一下合肥那个J我之前写的代码。。。现在对这个题，感觉更清晰了一些。

因为不管你路径怎么走，一定会有一个边来当最短的那个边，并且我们用 dijkstra 算出来的每个点到 \(1\) 和 \(n\) 的经过的最短的最大的边，这个东西也是保证一定正确的。

2023ICPC合肥区域赛J题 ¶

这个题简直是跟上面一题一模一样的，是去年十月份VP的，当时就不会，然后看了题解。但显然没怎么记住，但是能记得以前写过也是还算可以了哈哈哈。

这个题路径的权值是最大边加次大的边，我们同样不好求。那么我们直接枚举每一条边作为最大边，第二大的边肯定是 \(min(max(path(1, u), path(v, n)), max(path(1, v), path(u, n)))\)。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
const int INF = 1000000000;
const ll LNF = 1000000000000000000;
// #define int long long
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    vector<vector<pair<int,int>>>adj(n+1,vector<pair<int,int>>());
    vector<array<int,3>>edge(m);
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
        edge[i-1]={u,v,w};
    }
    auto dij=[&](int s){
        vector<int>dis(n+1,INF);
        priority_queue<pii,vector<pii>,greater<pii>>pq;
        dis[s]=0;
        pq.push({dis[s],s});
        while(!pq.empty()){
            auto [d,id]=pq.top();
            pq.pop();
            if(d>dis[id]) continue;
            for(auto [v,w]:adj[id]){
                int l=max(d,w);
                if(l<dis[v]){
                    dis[v]=l;
                    pq.push({dis[v],v});
                }
            }
        }
        return dis;
    };
    int ans=2*INF;
    vector dis1=dij(1),dis2=dij(n);
    for(auto [i,v,w]:edge){
        int y=min(max(dis1[i],dis2[v]),max(dis2[i],dis1[v]));
        if(y<=w)
            ans=min(ans,w+y);
    }
    cout<<ans<<'\n';
    return 0;
}

总结¶

这两题其实都不是很难，并且用的方法也是一模一样的。咋说呢，感觉想不出来也正常，但是下次真的不要想不到一样的题目了，虽然再遇见的概率很小。

总之就是要多思考吧，就算看题解，也起码自己尽量能多想到一些东西，这样印象会更深刻一些的。

CF2117G + 23合肥区域赛J¶

CF2117G¶

2023ICPC合肥区域赛J题¶

总结¶

CF2117G ¶

2023ICPC合肥区域赛J题 ¶