水题笔记_ [Noi2014]魔法森林 [图论, spfa, 动态加边]

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

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

懵逼的 题目

bmb

扯淡的 题解

一开始想这用二分$\max_b$然后加边跑最短路来着…

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

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

qwq

沙茶的 代码

然后…我把…INF赋小了…

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/**************************************************************
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