Bzoj 1922(最短路)

BZOJ 1922
题意:见上
有限制最短路
维护$d_1i$数组为到达$i$点的最短时间,$d_2i$数组为$i$点能到的最短时间。
实际到达时间为$max(d_1i, d_2i)$
dij 堆中以$d_1i, d_2i$为序做小根堆,每次取出一个点然后更新连边的$d_1$值,更新他保护点的$d_2$值,注意每个点没有保护才能更新$d_2$值,否则让这个点保护数目减一。

知识点
1、dij 维护几个数组来求有限制最短路很好用

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 3005;
const LL ZINF = 4223372036854775807ll;
struct edge {int u, v, w, nxt;} ed[70000 + 5];
struct node {
int u;
LL dis;
bool operator < (const node &b) const {return dis > b.dis;}
};
int n, m, en, hd[MAXN], num[MAXN], vis[MAXN];
LL d1[MAXN], d2[MAXN];
vector<int > ptc[MAXN];
priority_queue<node > q;
void ins(int u, int v, int w) {ed[++en] = (edge){u, v, w, hd[u]}, hd[u] = en;}
void dij() {
for (int i = 0; i <= n; ++i) vis[i] = 0, d1[i] = ZINF, d2[i] = 0;
d1[1] = d2[1] = 0, q.push((node){1, 0});
while (!q.empty()) {
node p = q.top(); q.pop();
if (vis[p.u]) continue ; vis[p.u] = 1;
LL rl = max(d1[p.u], d2[p.u]);
for (int i = hd[p.u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (rl + e.w < d1[e.v]) {
d1[e.v] = rl + e.w;
LL tmp = max(d1[e.v], d2[e.v]);
if (!num[e.v]) q.push((node){e.v, tmp});
}
}
for (int i = 0; i < (int)ptc[p.u].size(); ++i) {
int v = ptc[p.u][i];
d2[v] = max(d2[v], rl), --num[v];
if (!num[v]) q.push((node){v, max(d2[v], d1[v])});
}
}
}
void clean() {
en = 0, ms(hd, -1);
}
int solve() {
scanf("%d%d", &n, &m);
clean();
for (int u, v, w, i = 1; i <= m; ++i) scanf("%d%d%d", &u, &v, &w), ins(u, v, w);
for (int u = 1; u <= n; ++u) {
scanf("%d", &num[u]);
for (int v, i = 1; i <= num[u]; ++i) scanf("%d", &v), ptc[v].push_back(u);
}
dij();
printf("%lld\n", max(d1[n], d2[n]));//////////////////////////////////
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

------ 本文结束 ------