POJ_3635

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

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

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