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

2026年发布的题解！

能不能点个赞

---

首先简化题意：

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

然后就是写代码:

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

最后输出（write）：

• 输出最小值

完整代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
const int N = 5005;

struct node {
    int v, w, b;
};
vector<node> g[N];
int n, m;
struct En {
    int w, b;
} e[N];

int dij(int Free) {
    vector<int> dist(n + 1, INF);
    vector<bool> vis(n + 1, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> q;
    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 &[v, w, b] : g[u]) {
            if (Free != -1 && b > e[Free].b) continue;
            int cost = w;
            if (Free != -1 && w == e[Free].w && b == e[Free].b) {
                cost = 0;
            }
            if (dist[v] > d + cost) {
                dist[v] = d + cost;
                q.emplace(dist[v], v);
            }
        }
    }
    return dist[n];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v, w, b;
        cin >> u >> v >> w >> b;
        e[i] = {w, b};
        g[u].push_back({v, w, b});
        g[v].push_back({u, w, b});
    }
    int ans = INF;
    ans = min(ans, dij(-1));
    for (int i = 1; i <= m; ++i) {
        ans = min(ans, dij(i));
    }
    if (ans >= INF) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}
//AI改的，所以AI味儿可能有点重

---

🎉完结撒花🎉

这道题给绿高了