乘车路线
原题：（权限限制没有链接（我想应该是有的））
题目描述
编号为1.. N的N座城镇用若干单向行驶的道路相连，每条道路上均有两个参数：道路长度(length)和在该条道路上行驶的费用（cost）。BOB准备从城镇1出发到达城镇N，但他目前只有W的钱，为此，你需要帮助他寻找一条从城镇1到城镇N在他能支付的前提下的一条最短路线。
输入输出格式
输入格式：
W N K （N为城镇数目，2<=N<=100，K为道路条数，1<=K<=10000,W为钱的数目， 0<=w<=1000）
随后的K行每行为一条道路的信息，包含4个数值（S,D,L,T）其中S为源城镇，D为目标城镇，L为道路长度，T为所需支付用。（1<=S,D<=N,1<=L<=100,0<=T<=100）
输出格式：
输出最短长度，若无解，则输出“NO”；
输入输出样例
输入样例#1：
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
输出样例#1：
11
个人解法：
来做一下笔记。
将题目转换一下，就是：
一条边的信息为<u,v,ai,bi>，求在sigma(bi)不超过w的情况下求关于ai的最短路。
这个题就是一个朴素的二维SPFA（我也是第一次写二维SPFA）。
Dist[i,j]表示走到i的代价为j时的最短路。（开了二维数组）肯定是可以保证正确性的。
更新就是从Dist[i,j]+ai到Dist[k,j+bi]。
所以就按照Spfa来做就可以了。
代码如下：
type
Rec=record
x,ai,bi,next:longint;//bi是花费，ai是路程
end;
inf=record
x,ai,bi:longint;//队列也要记录x、ai与bi
end;
var
Arrmap:array[1..110] of longint;//存邻接链表
Arre:array[1..10000] of Rec;
Arr:array[1..1048576] of inf;//Spfa队列
Dist:array[1..100,0..2000] of longint;
Flag:array[1..100,0..2000] of boolean;
w,n,k,i,u,v,l,t,top,ans:longint;
procedure ins(f,s,ai,bi:longint);//插入一条边
begin
inc(top);
Arre[top].x:=s;
Arre[top].ai:=ai;
Arre[top].bi:=bi;
Arre[top].next:=Arrmap[f];
Arrmap[f]:=top;
end;
function Relax(u,v,ai,bu,bv:longint):boolean;//松弛
begin
if Dist[u,bu]+ai<Dist[v,bv] then
begin
Dist[v,bv]:=Dist[u,bu]+ai;
exit(true);
end
else exit(false);
end;
procedure Spfa(x:longint);//最短路
var
hi,ti,v,bi:longint;
begin
hi:=0;
ti:=1;
Arr[1].x:=1;
Flag[1,0]:=true;
Dist[1,0]:=0;
while hi<>ti do
begin
hi:=(hi and ((1 shl 20)-1))+1;
Flag[Arr[hi].x,Arr[hi].bi]:=false;
v:=Arrmap[Arr[hi].x];
while v<>0 do
begin
bi:=Arr[hi].bi+Arre[v].bi;//如果已经bi大于w了就不必更新了
if bi<=w then
if Relax(Arr[hi].x,Arre[v].x,Arre[v].ai,Arr[hi].bi,bi) then
if not Flag[Arre[v].x,bi] then
begin
ti:=(ti and ((1 shl 20)-1))+1;
Arr[ti].x:=Arre[v].x;
Arr[ti].ai:=Arr[hi].ai+Arre[v].ai;
Arr[ti].bi:=bi;
Flag[Arre[v].x,bi]:=true;
end;
v:=Arre[v].next;
end;
end;
end;
begin
read(w,n,k);//读入
for i:=1 to k do
begin
read(u,v,l,t);
ins(u,v,l,t);
end;
fillchar(Dist,sizeof(Dist),124);
Spfa(1);//跑最短路
ans:=2088533116;
for i:=0 to w do
if ans>Dist[n,i] then ans:=Dist[n,i];//计算答案
writeln(ans);//输出
end.
然而在考场上我还是写不出二维Spfa的。
于是就想乱搜一通。
起点开始，搜索出所有的路径，每一个路径拿出来，看bi是否超过w，如果没有，就拿出来和ans比较。
在一般的BFS中，我们可能会用一个flag数组来优化，之前扫到的点之后就不必再扫。在这里不能用flag数组，因为存在环与相交路径。
所以按照BFS来做，最后还可能衍生出一些不必要的路径（例如带环路径）。
所以搜索的复杂度是很大的。
那么怎么剪枝？
首先不难想到最优性剪枝。如果已经知道一条可行路径的ai值，那么就可以暂定为ans，之后若搜索到了大于ans的路径就不必继续拓展了。
也不难想到可行性剪枝。如果我们搜索到当前节点已经花费了bv的钱，而当前节点走到n的最少的花费为bi。如果bv+bi>w，也就不可行了。
接下来我们发现，一条可行路径与每个点到n的最小花费均可以通过一遍Dijkstral（Spfa）跑出来。
所以我们从终点n开始反着跑Dijkstral（Spfa），顺便找到一条可行路径。
同时，对于带环路径的处理，我们可以发现，若用(u,ai,bi)来表示状态，那么如果存在(v,5,6)之后，(v,7,8)就是完全没有用的了。所以这里还可以加一个剪枝，删去不必要的状态。这个剪枝可以减少许多带环路径的状态。
大概到这里就差不多可以过了。
代码如下：
type
Rec=record
x,cost,len,next:longint;
end;
inf=record
x,len,cost,last:longint;
end;
var
Precost,Dist,nowlen,nowcost:array[1..100] of longint;//Precost记录i到n的最少花费。nowlen与nowcost记录(u,max{ai},max{bi})，Dist是在反着跑Dijkstral时记录的路径。
Arrmap:array[0..1,1..100] of longint;//存图。0是正向图，1是反向图
Arr:array[1..3000000] of inf;//BFS数组
Arre:array[0..1,1..20010] of Rec;
Flag:array[1..100] of boolean;//反着跑Dijkstral时的判重数组
money,i,n,m,u,v,w,x,top,ans:longint;
procedure ins(ifdo,f,s,len,cost:longint);//插入一条边
begin
inc(top);
Arre[ifdo,top].x:=s;
Arre[ifdo,top].len:=len;
Arre[ifdo,top].cost:=cost;
Arre[ifdo,top].next:=Arrmap[ifdo,f];
Arrmap[ifdo,f]:=top;
end;
procedure BFS;//搜索
var
h,t:longint;
begin
h:=0;
t:=1;
Arr[1].x:=1;
fillchar(flag,sizeof(flag),false);//记录该点是否被遍历过。因为nowlen与nowdist只有在该点被遍历过之后才有意义。
Flag[1]:=true;
while h<>t do
begin
h:=(h and ((1 shl 21)-1))+1;
if Arr[h].cost+Precost[Arr[h].x]>money then continue;//如果当前状态的bi+当前节点到n的最小bi>money，就可以不必拓展了。
v:=Arrmap[0,Arr[h].x];
while v<>0 do
begin
if Arre[0,v].x=Arr[h].last then//如果这条边指回去，也就是二元一个环，可以不必拓展过去
begin
v:=Arre[0,v].next;
continue;
end;
if Arr[h].len+Arre[0,v].len>ans then//如果当前路程+边的路程>ans，可以不必拓展（最优性剪枝）
begin
v:=Arre[0,v].next;
continue;
end;
if Arr[h].cost+Arre[0,v].cost>money then//如果当前节点花费+到n的最小花费>money，可以不用拓展（可行性剪枝）
begin
v:=Arre[0,v].next;
continue;
end;
if Arre[0,v].x=n then//如果搜到了一条路径，更新答案
begin
if ans>Arr[h].len+Arre[0,v].len then
ans:=Arr[h].len+Arre[0,v].len;
v:=Arre[0,v].next;
continue;
end;
if flag[Arre[0,v].x] then//如果存在一个状态，len与cost均大于之前的一个状态，可以不必拓展
if (Arr[h].len+Arre[0,v].len>nowlen[Arre[0,v].x])
and (Arr[h].cost+Arre[0,v].cost>nowcost[Arre[0,v].x]) then
begin
v:=Arre[0,v].next;
continue;
end;
t:=(t and ((1 shl 21)-1))+1;//入队
Arr[t].x:=Arre[0,v].x;
Arr[t].len:=Arr[h].len+Arre[0,v].len;
Arr[t].cost:=Arr[h].cost+Arre[0,v].cost;
Arr[t].last:=Arr[h].x;
Flag[Arr[t].x]:=true;
if nowlen[Arr[t].x]<Arr[t].len
then nowlen[Arr[t].x]:=Arr[t].len;
if nowcost[Arr[t].x]<Arr[t].cost
then nowcost[Arr[t].x]:=Arr[t].cost;//更新nowlen与nowcost
v:=Arre[0,v].next;
end;
end;
end;
procedure Costdijkstral;//反着跑Dijkstral
var
vi,vj,v,p,minn:longint;
begin
fillchar(Precost,sizeof(Precost),124);
Precost[n]:=0;
Flag[n]:=true;
v:=Arrmap[1,n];
while v<>0 do
begin
if Precost[Arre[1,v].x]>Arre[1,v].cost then
begin
Precost[Arre[1,v].x]:=Arre[1,v].cost;
Dist[Arre[1,v].x]:=Arre[1,v].len;//顺便记录路径
end;
v:=Arre[1,v].next;
end;
for vi:=2 to n do
begin
minn:=2088533116;
for vj:=1 to n do
if (Precost[vj]<minn) and (not flag[vj]) then
begin
minn:=Precost[vj];
p:=vj;
end;
Flag[p]:=true;
v:=Arrmap[1,p];
while v<>0 do
begin
if Precost[p]+Arre[1,v].cost<Precost[Arre[1,v].x] then
begin
Precost[Arre[1,v].x]:=Precost[p]+Arre[1,v].cost;
Dist[Arre[1,v].x]:=Dist[p]+Arre[1,v].len;
end;
v:=Arre[1,v].next;
end;
end;
end;
begin
read(money,n,m);//读入
for i:=1 to m do
begin
read(u,v,w,x);
if u=v then continue;
ins(0,u,v,w,x);
ins(1,v,u,w,x);
end;
Costdijkstral;//求最优性剪枝与可行性剪枝的条件。
if Precost[1]>money then//如果1到n的最少花费都比money大，就可以判断无解了。
begin
writeln('NO');
halt;
end;
ans:=Dist[1];
BFS;//搜索
writeln(ans);//输出答案
end.
不得不说，加了3个剪枝以后，跑得的确还不慢。跑二维Spfa最大数据要249ms，然而搜索最大数据4ms……
不过主要还是学二维Spfa，长知识了。