学步园

三次SPFA，第一次和第二次反向建图，求出任意点到终点最短路，第三次以报警次数为关键字进行SPFA。

#include<algorithm>  
#include<iostream>  
#include<cstring>  
#include<cstdio>  
#define inf 0x7fffffff  
#define MAXN 100001
using namespace std;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x*f;
}

struct edge {
    int to, next, v1, v2;
} e[MAXN], d[MAXN];
int n, m, cnt, ans, u[MAXN], v[MAXN], w1[MAXN], w2[MAXN], d1[10001], d2[10001], dis[10001], head[10001], h[10001];

void ins(int u, int v, int w1, int w2) {
    e[++cnt] = (edge){v, head[u], w1, w2};
    head[u] = cnt;
}

void spfa1() {
    int q[MAXN], t = 0, w = 0;
    bool inq[10001];
    memset(inq, 0, sizeof (inq));
    memset(d1, 127, sizeof (d1));
    d1[n] = 0;
    q[0] = n;
    inq[n] = 1;
    while (t <= w) {
        int now = q[t++];
        for (int i = head[now]; i; i = e[i].next) {
            if (d1[now] + e[i].v1 < d1[e[i].to]) {
                d1[e[i].to] = d1[now] + e[i].v1;
                if (!inq[e[i].to]) {
                    q[++w] = e[i].to;
                    inq[e[i].to] = 1;
                }
            }
        }
        inq[now] = 0;
    }
}

void spfa2() {
    int q[MAXN], t = 0, w = 0;
    bool inq[10001];
    memset(inq, 0, sizeof (inq));
    memset(d2, 127, sizeof (d2));
    d2[n] = 0;
    q[0] = n;
    inq[n] = 1;
    while (t <= w) {
        int now = q[t++];
        for (int i = head[now]; i; i = e[i].next) {
            if (d2[now] + e[i].v2 < d2[e[i].to]) {
                d2[e[i].to] = d2[now] + e[i].v2;
                if (!inq[e[i].to]) {
                    q[++w] = e[i].to;
                    inq[e[i].to] = 1;
                }
            }
        }
        inq[now] = 0;
    }
}

void spfa3() {
    int q[MAXN], t = 0, w = 0;
    bool inq[10001];
    memset(inq, 0, sizeof (inq));
    memset(dis, 127, sizeof (dis));
    dis[1] = 0;
    q[0] = 1;
    inq[1] = 1;
    while (t <= w) {
        int now = q[t++];
        for (int i = h[now]; i; i = d[i].next) {
            if (dis[now] + d[i].v1 < dis[d[i].to]) {
                dis[d[i].to] = dis[now] + d[i].v1;
                if (!inq[d[i].to]) {
                    q[++w] = d[i].to;
                    inq[e[i].to] = 1;
                }
            }
        }
        inq[now] = 0;
    }
}

int main() {
    n = read();
    m = read();
    for (int i = 1; i <= m; i++) {
        u[i] = read();
        v[i] = read();
        w1[i] = read();
        w2[i] = read();
        ins(v[i], u[i], w1[i], w2[i]);
    }
    spfa1();
    spfa2();
    for (int i = 1; i <= m; i++) {
        d[i].to = v[i];
        d[i].next = h[u[i]];
        h[u[i]] = i;
        if (d1[v[i]] + w1[i] > d1[u[i]])d[i].v1++;
        if (d2[v[i]] + w2[i] > d2[u[i]])d[i].v1++;
    }
    spfa3();
    printf("%d", dis[n]);
    return 0;
}