#62 - 63 答案比输出多 $1$

#64 - 66 答案比输出多 $2$

尝试 + rand()%3 最优情况只错 $4$ 个点

qwq 求条

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
using ll = long long;
const int N = 205, M = 5e4 + 5;
const ll inf = 2e18;
ll dis1[N], dis2[N], dis3[N], dis4[N], dis5[N], dis6[N];
int fa1[N], fa2[N], mrk1[M], mrk2[M];
int delnum, addu, addv, addw;
int p[M], w[M];
pii e[M];
vector<pii> g1[N], g2[N];
vector<int> num[N];
int n, m;

void dij(int s, vector<pii> *g, int zt) {
    vector<ll> dis(n + 5, inf);
    vector<int> vis(n + 5);
    dis[s] = 0;
    priority_queue<pair<ll, int>> q;
    q.push({0, s});
    while (!q.empty()) {
        ll d = -q.top().first;
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        // 添加反向边处理
        if (u == addu && d + addw < dis[addv]) {
            dis[addv] = d + addw;
            q.push({-dis[addv], addv});
        }
        int pos = 0;
        for (auto x : g[u]) {
            int v = x.first, w = x.second;
            // 修复：跳过删除边后仍需 pos++
            if (zt >= 5 && num[u][pos] == delnum) {
                pos++;
                continue;
            }
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                // 仅记录前驱节点
                if (zt == 1) fa1[v] = u;
                if (zt == 2) fa2[v] = u;
                q.push({-dis[v], v});
            }
            pos++;
        }
    }
    // 存储结果
    for (int i = 1; i <= n; i++) {
        if (zt == 1) dis1[i] = dis[i];
        if (zt == 2) dis2[i] = dis[i];
        if (zt == 3) dis3[i] = dis[i];
        if (zt == 4) dis4[i] = dis[i];
        if (zt == 5) dis5[i] = dis[i];
        if (zt == 6) dis6[i] = dis[i];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("P6880_62.in", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v >> w[i] >> p[i];
        g1[u].pb({v, w[i]});
        num[u].pb(i);
        g2[v].pb({u, w[i]});
        e[i] = {u, v};
    }
    
    // 初始 Dijkstra
    dij(1, g1, 1);
    dij(n, g1, 2);
    dij(1, g2, 3);
    dij(n, g2, 4);

    // 回溯标记 1->n 路径
    if (dis1[n] < inf) {
        int uu = n;
        while (uu != 1) {
            int prev = fa1[uu];
            ll mxs = inf;
            // 找到连接 prev->uu 的边
            for (int i = 0; i < g1[prev].size(); i++) {
                if (g1[prev][i].first == uu && g1[prev][i].second < mxs) {
                    mrk1[num[prev][i]] = 1;
                    mxs = g1[prev][i].second;
                    break;
                }
            }
            uu = prev;
        }
    }

    // 回溯标记 n->1 路径
    if (dis2[1] < inf) {
        int uu = 1;
        while (uu != n) {
            int prev = fa2[uu];
            ll mxs = inf;
            for (int i = 0; i < g1[prev].size(); i++) {
                if (g1[prev][i].first == uu && g1[prev][i].second < mxs) {
                    mrk2[num[prev][i]] = 1;
                    mxs = g1[prev][i].second;
                    break;
                }
            }
            uu = prev;
        }
    }

    ll mincost = dis1[n] + dis2[1];
    for (int i = 1; i <= m; i++) {
        int u = e[i].first, v = e[i].second;
        if (mrk1[i] || mrk2[i]) {
            delnum = i;
            addu = v;
            addv = u;
            addw = w[i];
            // 关键修复：对修改后的图计算双路径
            dij(1, g1, 5);  // 1->n 在新图
            dij(n, g1, 6);  // n->1 在新图
            mincost = min(mincost, dis5[n] + dis6[1] + p[i]);
        } else {
            // 非最短路径边
            ll path1 = min(dis1[n], dis1[v] + dis4[u] + w[i]);
            ll path2 = min(dis2[1], dis2[v] + dis3[u] + w[i]);
            mincost = min(mincost, path1 + path2 + p[i]);
        }
    }
    cout << (mincost >= inf ? -1 : mincost) << '\n';
    return 0;
}