POJ_1724
这个题目可以直接将SPFA中的dis[]变成二维的dis[i][k]表示到第i个点花费为k时的最短路，但如果直接做SPFA会超时，需要加一个剪枝：设mind[i]表示到第i个点的用于剪枝最短路，mink[i] 表示第i个点的用于剪枝的最小花费，如果在SPFA的过程中走到了第i个点的路径长为d花费为k，那么如果d>=mind[i]&&k>=mink[i]，这时就进行剪枝，如果d<mind[i]&&k<mink[i]就更新mind[i]与mink[i]的值，并将这个点(i,k)入队，其余的情况也要将(i,k)入队。
这个题目还可以用堆形式的SPFA去做，这时需要把N个点看成N*(K+1)个点，且堆顶的元素为当前所有点中dis[]的值最小的一个。其余的操作和SPFA大体相同，这时同样有一个剪枝：如果堆顶的元素是标号为N的点，那么就可以直接结束SPFA了。
//普通的SPFA
#include<stdio.h>
#include<string.h>
#define MAXD 110
#define MAXK 10010
#define MAXM 10010
#define MAXQ 1000110
#define INF 0x3f3f3f3f
int N, M, K, first[MAXD], next[MAXM], v[MAXM], w[MAXM], cost[MAXM], e, q[MAXQ], m[MAXQ], inq[MAXD][MAXK], d[MAXD][MAXK], mind[MAXD], mink[MAXD], Q = 1000100;
void add(int &x, int &y, int &z, int &t)
{
v[e] = y;
w[e] = z;
cost[e] = t;
next[e] = first[x];
first[x] = e;
++ e;
}
void init()
{
int i, j, k, x, y, z, t;
e = 0;
memset(first, -1, sizeof(first));
scanf("%d%d", &N, &M);
for(i = 0; i < M; i ++)
{
scanf("%d%d%d%d", &x, &y, &z, &t);
add(x, y, z, t);
}
}
void solve()
{
int i, j, k, x, y, z, newk, front ,rear, ans;
front = rear = 0;
for(i = 1; i <= N; i ++)
for(j = 0; j <= K; j ++)
d[i][j] = INF, inq[i][j] = 0;
memset(mind, 0x3f, sizeof(mind));
memset(mink, 0x3f, sizeof(mink));
q[rear] = 1, m[rear] = 0, d[1][0] = 0;
++ rear;
mind[1] = mink[1] = 0;
while(front != rear)
{
x = q[front], k = m[front];
inq[x][k] = 0;
++ front;
if(front > Q)
front = 0;
for(i = first[x]; i != -1; i = next[i])
{
y = v[i], newk = k + cost[i], z= d[x][k] + w[i];
if(newk <= K && z < d[y][newk])
{
if(z >= mind[y] && newk >= mink[y])
continue;
if(z < mind[y] && newk < mink[y])
mind[y] = z, mink[y] = newk;
d[y][newk] = z;
if(!inq[y][newk])
{
q[rear] = y;
m[rear] = newk;
inq[y][newk] = 1;
++ rear;
if(rear > Q)
rear = 0;
}
}
}
}
ans = INF;
for(i = 0; i <= K; i ++)
if(d[N][i] < ans)
ans = d[N][i];
printf("%d\n", ans == INF ? -1 : ans);
}
int main()
{
while(scanf("%d", &K) == 1)
{
init();
solve();
}
return 0;
}
//堆形式的SPFA
#include<stdio.h>
#include<string.h>
#define MAXD 110
#define MAX 4000410
#define MAXM 10010
#define INF 0x3f3f3f3f
int N, M, K, first[MAXD], next[MAXM], v[MAXM], w[MAXM], cost[MAXM], P, f[MAX], d[MAX], m[MAX], tree[MAX], mind[MAXD], mink[MAXD];
void init()
{
int i, j, k, x, y, z, t;
memset(first, -1, sizeof(first));
scanf("%d%d", &N, &M);
for(i = 0; i < M; i ++)
{
scanf("%d%d%d%d", &x, &y, &z, &t);
v[i] = y;
w[i] = z;
cost[i] = t;
next[i] = first[x];
first[x] = i;
}
}
void insert(int cur, int dis, int k)
{
int i, left, right, s = k * N + cur;
if(dis < d[s])
{
f[s] = cur;
d[s] = dis;
m[s] = k;
i = P + s;
if(!tree[i])
{
tree[i] = s;
for(i >>= 1; i > 0; i >>= 1)
{
left = tree[2 * i], right = tree[2 * i + 1];
tree[i] = d[left] < d[right] ? left : right;
}
}
}
}
void update()
{
int i, left, right, s = tree[1];
i = P + s;
tree[i] = 0;
for(i >>= 1; i > 0; i >>= 1)
{
left = tree[2 * i], right = tree[2 * i + 1];
tree[i] = d[left] < d[right] ? left : right;
}
}
void solve()
{
int i, j, k, x, y, z, s, t, ans;
memset(mind, 0x3f, sizeof(mind));
memset(mink, 0x3f, sizeof(mink));
for(P = 1; P < (K + 1) * N + 2; P <<= 1);
for(i = (K + 1) * N; i >= 0; i --)
d[i] = INF;
for(i = 2 * P - 1; i > 0; i --)
tree[i] = 0;
d[0] = m[0] = INF;
insert(1, 0, 0);
mind[1] = mink[1] = 0;
while(tree[1])
{
s = tree[1];
if(s % N == 0)
break;
update();
x = f[s], k = m[s];
for(i = first[x]; i != -1; i = next[i])
{
y = v[i], z = d[s] + w[i], t = k + cost[i];
if(t <= K)
{
if(z >= mind[y] && t >= mink[y])
continue;
if(z < mind[y] && t < mink[y])
mind[y] = z, mink[y] = t;
insert(y, z, t);
}
}
}
printf("%d\n", tree[1] ? d[s] : -1);
}
int main()
{
while(scanf("%d", &K) == 1)
{
init();
solve();
}
return 0;
}