POJ 3463 Sightseeing

POJ_3463
タイトルは最短ルートと最短ルートより1大きいすべての経路の数を求めることを要求します.
最短ルートの数だけを求めると、SPFA+dpまたはdij+dpで直接行うことができますが、この問題は二次短絡に相当する数の問題が1つ増えたにすぎません.そのため、各点を2つの点に分割し、1つの点は最短ルートの距離と経路の数を記録し、もう1つは二次短絡距離と経路の数を記録することができます.dij+dpで処理するのはもっと便利だと思います.
更新するたびに、最短よりも小さい場合は、二次短絡に関するデータを先に前の最短のデータに更新してから、最短のデータを更新し、最短より大きいが二次短絡より小さい場合は二次短絡のデータを更新するだけで、他の場合は分析しやすい.

#include<stdio.h>
#include<string.h>
#define MAXD 1010
#define MAXM 10010
#define INF 0x3f3f3f3f
int N, M, D, S, T, e, first[MAXD], next[MAXM], v[MAXM], w[MAXM], tree[8 * MAXD], d[2 * MAXD], ans[2 * MAXD];
void init()
{
    int i, j, k, x, y, z;
    e = 0;
    scanf("%d%d", &N, &M);
    memset(first + 1, -1, sizeof(first[0]) * N);
    for(i = 0; i < M; i ++)
    {
        scanf("%d%d%d", &x, &y, &z);
        v[e] = y, w[e] = z;
        next[e] = first[x];
        first[x] = e;
        ++ e;
    }
}
void update(int i)
{
    for(; i ^ 1; i >>= 1)
        tree[i >> 1] = d[tree[i]] < d[tree[i ^ 1]] ? tree[i] : tree[i ^ 1];
}
void solve()
{
    int i, j, k, x, y1, y2;
    for(D = 1; D < 2 * N + 4; D <<= 1);
    memset(d, 0x3f, sizeof(d));
    memset(tree, 0, sizeof(tree));
    for(i = 2; i <= 2 * N + 1; i ++)
        tree[D + i] = i;
    scanf("%d%d", &S, &T);
    d[S << 1] = 0;
    ans[S << 1] = 1;
    update(D + (S << 1));
    while(d[tree[1]] != INF)
    {
        x = tree[1];
        if(x == ((T << 1) ^ 1))
            break;
        for(i = first[x >> 1]; i != -1; i = next[i])
        {
            y1 = v[i] << 1, y2 = (v[i] << 1) ^ 1;
            if(d[x] + w[i] <= d[y1])
            {
                if(d[x] + w[i] < d[y1])
                {
                    d[y2] = d[y1], ans[y2] = ans[y1];
                    update(D + y2);
                    d[y1] = d[x] + w[i], ans[y1] = ans[x];
                    update(D + y1);
                }
                else
                    ans[y1] += ans[x];
            }
            else if(d[x] + w[i] <= d[y2])
            {
                if(d[x] + w[i] < d[y2])
                {
                    d[y2] = d[x] + w[i], ans[y2] = ans[x];
                    update(D + y2);
                }
                else
                    ans[y2] += ans[x];
            }
        }
        tree[x + D] = 0;
        update(x + D);
    }
    printf("%d
", ans[T << 1] + (d[(T << 1) ^ 1] == d[T << 1] + 1 ? ans[(T << 1) ^ 1] : 0));
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t --)
    {
        init();
        solve();
    }
    return 0;
}