「Bzoj 1922」「Sdoi2010」大陆争霸 (最短路)

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 维护几个数组来求有限制最短路很好用

#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;
}