数据结构: 明明是我先来的

L什么T啊? LC什么? 什么CT?

懵逼的 题目

bmb

扯淡的 题解

一开始想这用二分$\max_b$然后加边跑最小生成树来着…

然后看dalao写的动态加边SPFA感觉非常劲啊…那就SPFA吧…

最后 $from\,\,rqy$的 [最小瓶颈路可以用最短路算法的证明] (当年loli非说瓶颈路不能用dijk做哼唧)

qwq

沙茶的 代码

然后…我把…INF赋小了…

我直接INF = 50000忘了他是要把$a$和$b$加起来…

/**************************************************************
    Problem: 3669
    User: Cansult
    Language: C++
    Result: Accepted
    Time:2616 ms
    Memory:7548 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN (50000 + 5)
#define MAXM (100000 + 5)
#define INF (10000000 + 5)
#define pii pair<int, int>
#define mkp(a, b) make_pair(a, b)
using namespace std;
struct cmp
{
    bool operator () (const pii x, const pii y)
    { return x.second > y.second; }
};
struct edg
{
    int from, to, costa, costb, next;
    edg() {}
    edg(int fr, int dqt, int ca, int cb, int nex): from(fr), to(dqt), costa(ca), costb(cb), next(nex) {}
}b[MAXM << 1], e[MAXM];
int cntb, g[MAXN], n, m, dis[MAXN], ans = INF;
inline int max(const int x, const int y)
{
    if (x > y)   return x;
    else    return y;
}
bool cmpb(edg x, edg y)
{ return x.costb < y.costb; }
inline void adn(int from, int to, int costa, int costb)
{
    b[++cntb] = edg(from, to, costa, costb, g[from]);
    g[from] = cntb; 
}
void solve()
{
    queue<int> q;
    bool inq[MAXN]; 
    sort(e + 1, e + m + 1, cmpb);
    memset(inq, false, sizeof(inq));
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    for (int i = 1; i <= m; i++)
    {
        adn(e[i].from, e[i].to, e[i].costa, e[i].costb);
        adn(e[i].to, e[i].from, e[i].costa, e[i].costb);
        if (dis[e[i].to] > max(dis[e[i].from], e[i].costa))
            dis[e[i].to] = max(dis[e[i].from], e[i].costa), inq[e[i].to] = true, q.push(e[i].to);
        if (dis[e[i].from] > max(dis[e[i].to], e[i].costa))
            dis[e[i].from] = max(dis[e[i].to], e[i].costa), inq[e[i].from] = true, q.push(e[i].from);
        while (!q.empty())
        {
            int dq = q.front();
            q.pop();
            inq[dq] = false;
            for (int j = g[dq]; j; j = b[j].next)
                if (dis[b[j].to] > max(dis[dq], b[j].costa))
                {
                    dis[b[j].to] = max(dis[dq], b[j].costa);
                    if (!inq[b[j].to])
                        q.push(b[j].to), inq[b[j].to] = true;
                }
        }
        if (dis[n] < INF)
            ans = min(ans, e[i].costb + dis[n]);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d%d", &e[i].from, &e[i].to, &e[i].costa, &e[i].costb);
    solve();
    if (ans < INF)
        printf("%d\n", ans);
    else
        puts("-1");
    return 0;
}

By TJM小姐姐的后宫 Cansult