大家好，我是энтджей，今天是我2026年第十七次正式发题解！

2026年发布的题解！

能不能点个赞

---

首先简化题意：

• 说白了题意没什么好简化的

然后就是写代码:

• 这道题我认为是最好想但不那么好实现的题：
  • 其实就是用迪杰斯特拉来写，枚举所有免费边（可以没有）的情况，求最小值

最后输出（write）：

• 输出最小值

完整代码：

#include<bits/stdc++.h>
#define int long long  
using namespace std;
const int N = 5010;
const int INF = 1e18;
int n, m;
struct node {
    int v, w, b;
};
vector<node> g[N];
vector<int> bs;

int dij(int mf) {
    int dist[N];
    bool vis[N];
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> q;
    memset(vis, false, sizeof vis);
    fill(dist, dist + N, INF);
    dist[1] = 0;
    
    q.emplace(0, 1);
    while (!q.empty()) {
        auto [d, u] = q.top(); 
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto &e : g[u]) {
            if (e.b > mf) continue;
            int cost = (e.b == mf) ? 0 : e.w;
            if (dist[e.v] > d + cost) {
                dist[e.v] = d + cost;
                q.emplace(dist[e.v], e.v);
            }
        }
    }
    return dist[n];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, w, b;
        cin >> u >> v >> w >> b;
        g[u].push_back({v, w, b});
        g[v].push_back({u, w, b});
        bs.push_back(b);
    }
    sort(bs.begin(), bs.end());
    bs.erase(unique(bs.begin(), bs.end()), bs.end());
    int ans = INF;
    for(auto bi : bs)  {
        ans = min(ans, dij(bi));
    }
    if(ans < INF) cout << ans;
    else cout << -1;
    return 0;
}

---

🎉完结撒花🎉

这道题给绿高了