水题笔记_ 分层图集合 [图论, 分层图, 最短路]

今天被loli的板子模拟赛AprilFool了一波…非常难受…于是…

水题愉♂悦身心

卑怯的人,即使有万丈的怒火,除弱草以外,又能烧掉什么呢? ——鲁迅

[BeiJing wc2012]冻结

我居然也忘了priority_queuecmp是反着的…好久没写最短路了…

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (500000 + 5)
#define MAXM (500000 + 5)
#define INF (0X7FFFFFF)
#define MAXK (50)
#define bh(x, i) (((i) * MAXK) + x)
#define pii pair<int, int>
int dis[MAXN];
using namespace std;
struct edg
{
int from, to, next, cost;
}b[MAXM << 1];
struct cmp
{
bool operator () (const pii x, const pii y)
{
return x.second > y.second;
}
};
int g[MAXN], cntb, n, m, k;
void dijk()
{
bool vis[MAXN];
memset(vis, false, sizeof(vis));
memset(dis, 0x7f, sizeof(dis));
priority_queue<pii, vector<pii>, cmp> q;
q.push(make_pair(bh(1, 0), 0));
dis[1] = 0;
while (!q.empty())
{
pii dq = q.top();
q.pop();
if (vis[dq.first])
continue;
vis[dq.first] = true;
for (int i = g[dq.first]; i; i = b[i].next)
if (dis[b[i].to] > dis[dq.first] + b[i].cost)
{
dis[b[i].to] = dis[dq.first] + b[i].cost;
q.push(make_pair(b[i].to, dis[b[i].to]));
}
}
}
void adn(int from, int to, int cost)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
b[cntb].cost = cost;
g[from] = cntb;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; i++)
{
int srx, sry, srz;
scanf("%d%d%d", &srx, &sry, &srz);
for (int j = 0; j <= k; j++)
{
adn(bh(srx, j), bh(sry, j), srz);
adn(bh(sry, j), bh(srx, j), srz);
if (j != k)
{
adn(bh(srx, j), bh(sry, j + 1), srz >> 1);
adn(bh(sry, j), bh(srx, j + 1), srz >> 1);
}
}
}
dijk();
int ans = INF;
for (int i = 0; i <= k; i++)
ans = min(ans, dis[bh(n, i)]);
printf("%d", ans);
return 0;
}

/*
4 4 1
1 2 4
4 2 6
1 3 8
3 4 8
*/

[JLOI2011]飞行路线

注意这个题数据毒啊…把MAXN开大点才行啊…

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
92
93
94
95
96
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define INF (0X7FFFFFF)
#define MAXN (1000000 + 5)
#define MAXM (5000000 + 5)
#define MAXK (10000)
#define bh(x, i) (MAXK * (i) + x)
#define pii pair<int, int>
using namespace std;
int s, t;
struct cmp
{
bool operator () (const pii x, const pii y)
{
return x.second > y.second;
}
};
struct edg
{
int from, to, next, cost;
}b[MAXM];
int g[MAXN], cntb, n, m, k, dis[MAXN];
void adn(int from, int to, int cost)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
b[cntb].cost = cost;
g[from] = cntb;
}
void dijk()
{
bool vis[MAXN];
memset(dis, 0x7f, sizeof(dis));
memset(vis, false, sizeof(vis));
priority_queue<pii, vector<pii>, cmp> q;
q.push(make_pair(bh(s, 0), 0));
dis[bh(s, 0)] = 0;
while (!q.empty())
{
pii dq = q.top();
q.pop();
if (vis[dq.first])
continue;
vis[dq.first] = true;
for (int i = g[dq.first]; i; i = b[i].next)
if (dis[b[i].to] > dis[dq.first] + b[i].cost)
{
dis[b[i].to] = dis[dq.first] + b[i].cost;
q.push(make_pair(b[i].to, dis[b[i].to]));
}
}
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
scanf("%d%d", &s, &t);
++s, ++t;
for (int i = 1; i <= m; i++)
{
int srx, sry, srz;
scanf("%d%d%d", &srx, &sry, &srz);
++srx, ++sry;
for (int j = 0; j <= k; j++)
{
adn(bh(srx, j), bh(sry, j), srz);
adn(bh(sry, j), bh(srx, j), srz);
if (j != k)
{
adn(bh(srx, j), bh(sry, j + 1), 0);
adn(bh(sry, j), bh(srx, j + 1), 0);
}
}
}
dijk();
int ans = INF;
for (int i = 0; i <= k; i++)
ans = min(ans, dis[bh(t, i)]);
printf("%d", ans);
return 0;
}

/*
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100
*/

By 怯懦的 Cansult