【题解】[NOI2014] 魔法森林 SPFA 瞎搞 luogu – 2387 —quhengyi11

传送门：[NOI2014] 魔法森林

题意：给一张 $n$个点 $m$条边的无向图，每个边有两个边权 $A_i$和 $B_i$，求一条从 $1$到 $n$的 $Path$，使得 $\forall edge_i \in Path\;Max(A_i)+Max(B_i)$最小,$n\leq 5w,m\leq 10w$

听说这是一道 lct 模板题，但作为一个数据结构薄弱选手我肯定是不会 lct 的 QAQ

于是我们可以魔改 SPFA

解法 1：
枚举边权 $A_i$的最大值 $A_{max}$，将所有 $A_i\leq A_{max}$的边全部加进队列，然后将 $B_i$作为边权跑 SPFA~
复杂度:$\Theta(knm)$

那咋整呀，要算上述所有情况的最短路是不可避免的吧？
——所以我们可以尝试动态加边啦~

解法 2：
首先将权值 $A$排序，从小到大依次取边，那么我们会发现每次加入的边就那 1 条，何必再跑一次 SPFA 呢？但是我们要思考一下如何动态加边，SPFA 有一个队列，里面的元素都是有机会对整张图再次进行松弛操作的（从而进一步优化 $dis[]$的权值大小），我们不妨在加边的时候判断一下它连接的两个点是否可以通过它进行松弛操作（就这道题而言就是 $max(dis[u],e[u][v])<dis[v]$）如果可以进行松弛操作就将它加入队列，然后对这条边跑一边 SPFA 即可更新全图。

时间复杂度是:$\Theta(kn)$

代码:

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define mod 1000000007
#define ll long long
#define M 210005
#define N 50005
#define inf (1 << 29)
struct IN{
    int x, y, a, b;
    friend inline bool operator < (IN const &x, IN const &y)
    {
        return x.a < y.a;
    }
}in[M >> 1];
struct edge{
    int to, nxt, b;
}e[M];
int n, m, tot, d[N], head[N], ans = inf;
struct node{
    int d, pos;
    friend inline bool operator < (const node &x, const node &y)
    {
        return x.d > y.d;
    }
};
std::priority_queue <node> q;
inline void addedge (int u, int v, int b)
{
    e[++tot] = (edge) {v, head[u], b};
    head[u] = tot;
    e[++tot] = (edge) {u, head[v], b};
    head[v] = tot;
}
inline void spfa ()
{
    while (!q.empty())
    {
        node u = q.top(); q.pop();
        while (u.d != d[u.pos] && !q.empty())
        {
            u = q.top();
            q.pop();
        }
        if (q.empty() && u.d != d[u.pos]) break;
        for (int i = head[u.pos]; i; i = e[i].nxt)
        {
            int v = e[i].to;
            if (std::max(d[u.pos], e[i].b) < d[v])
            {
                d[v] = std::max(d[u.pos], e[i].b);
                q.push((node) {d[v], v});
            }
        }
    }
}
int main ()
{
    scanf("%d %d", &n, &m);
    fo (i, 1, m)
        scanf("%d %d %d %d", &in[i].x, &in[i].y, &in[i].a, &in[i].b);
    std::sort(in + 1, in + m + 1);
    fo (i, 2, n) d[i] = inf;
    fo (i, 1, m)
    {
        addedge(in[i].x, in[i].y, in[i].b);
        int u = in[i].x, v = in[i].y;
        if (d[u] > d[v]) std::swap(u, v);
        if (std::max(d[u], in[i].b) < d[v])
        {
            d[v] = std::max(d[u], in[i].b);
            q.push((node) {d[v], v});
            spfa();
        }
        ans = std::min(ans, d[n] + in[i].a);
    }
    if (ans == inf)
        printf("-1");
    else
        printf("%d", ans);
    return 0;
}