学步园

POJ_3635

    可以把图上一个点拆成C+1个点然后直接应用dij即可，同时总状态是一定的，为了减少每一步的决策量，我们可以每次加油都只加1个单位。

    貌似这样的题目用dij都会比SPFA快一些，因为状态比较多，而dij搜到终点就可以退出，这样相比SPFA减少了对很多无用状态的搜索量。

#include<stdio.h>
#include<string.h>
#define MAXD 1010
#define MAXM 20010
#define MAXC 110
#define MAXT 110000
#define INF 0x3f3f3f3f
int N, M, Q, D, S, E, C, e, cost[MAXD], first[MAXD], next[MAXM], v[MAXM], w[MAXM];
int f[MAXT], tree[4 * MAXT];
void update(int i)
{
for(; i ^ 1; i >>= 1)
        tree[i >> 1] = f[tree[i]] < f[tree[i ^ 1]] ? tree[i] : tree[i ^ 1];
}
void new_edge(int x, int y, int z)
{
    v[e] = y, w[e] = z;
    next[e] = first[x], first[x] = e;
    ++ e;
}
void init()
{
int i, j, k, x, y, z;
for(i = 0; i < N; i ++)
        scanf("%d", &cost[i]);
    memset(first, -1, sizeof(first[0]) * N);
    e = 0;
for(i = 0; i < M; i ++)
    {
        scanf("%d%d%d", &x, &y, &z);
        new_edge(x, y, z), new_edge(y, x, z);
    }
}
int get_id(int x, int c)
{
return x * (C + 1) + c + 1;
}
void divide_id(int id, int &x, int &c)
{
    c = (id - 1) % (C + 1);
    x = (id - 1) / (C + 1);
}
void solve()
{
int i, j, k, x, c, id;
    scanf("%d", &Q);
for(k = 0; k < Q; k ++)
    {
        scanf("%d%d%d", &C, &S, &E);
for(D = 1; D < N * (C + 1); D <<= 1);
        memset(f + 1, 0x3f, sizeof(f[0]) * (N * (C + 1)));
        f[0] = INF;
        memset(tree + 1, 0, sizeof(tree[0]) * (D << 1));
        j = get_id(S, 0);
        f[j] = 0, tree[j + D] = j, update(j + D);
while(id = tree[1])
        {
            divide_id(id, x, c);
if(x == E)
break;
            tree[D + id] = 0, update(D + id);
if(c < C)
            {
                j = get_id(x, c + 1);
if(f[id] + cost[x] < f[j])
                {
                    f[j] = f[id] + cost[x];
                    tree[j + D] = j, update(j + D);
                }
            }
for(i = first[x]; i != -1; i = next[i])
if(c >= w[i])
                {
                    j = get_id(v[i], c - w[i]);
if(f[id] < f[j])
                    {
                        f[j] = f[id];
                        tree[j + D] = j, update(j + D);
                    }
                }
        }
if(tree[1] == 0)
            printf("impossible\n");
else
            printf("%d\n", f[tree[1]]);
    }
}
int main()
{
while(scanf("%d%d", &N, &M) == 2)
    {
        init();
        solve();
    }
return 0;
}