1756 【差分约束】Candies(糖果).doc

文档介绍：【差分约束】Candies(糖果)
Time Limit:1000MS  Memory Limit:65536K
Total Submit:5 Accepted:5
Description
糖果()
【问题描述】
在幼儿园的日子,flymouse是班长。有时班主任带来了一大包糖果,并让flymouse分发。所有的孩子们非常喜爱糖果和经常比较他们得到糖果数目与其他人的数目。对一个孩子A,他觉得自己得到的糖果不应少于班上的B,否则他会去班主任那里抱怨flymouse偏心。
Snoopy当时与flymouse同班。flymouse总是与Snoopy比较糖果数量。现在flymouse想知道,保证他不被其他同学抱怨的情况下,他能比Snoopy多几个糖果?
Input
第一行有两个整数N,M,其中1 ≤ N ≤ 30000,1 ≤ M ≤ 150000。N表示班上孩子的数量,孩子分别编号为1..N,Snoopy编号为1,flymouse编号为N。
接下来M行,每行有三个整数A,B,c,表示A觉得自己得到的糖果不能比B得到的糖果少c个。
Output
输出flymouse最多比Snoopy多的糖果数量。保证有解。
Sample Input
2 2
1 2 5
2 1 4
Sample Output
5
Hint
保证数据在32位的范围内
本题数据不完整,请在本系统测试通过后到/problem?id=3159 提交完整测试!
Source
POJ Monthly--, Sempr
解析:
最短路径
Bellman-Ford超时, Dijkstra算法可以高效解决, SPFA(队列)居然超时...SPFA修改为堆栈实现就过了.
程序1:
const maxn=30001;
var i,j,k,n,m,s,l:longint;
a:array[0..150001,0..2] of longint;
b,d,q:array[0..maxn] of longint;
v:array[0..maxn] of boolean;
procedure spfa;
var t,i,j,k:longint;
begin
t:=1;
fillchar(d,sizeof(d),$7);
d[1]:=0; q[1]:=1;
v[1]:=true;
while t>0 do begin
i:=q[t]; dec(t);
k:=b[i];
while k<>0 do begin
j:=a[k,1];
if d[i]+a[k,2]<d[j] then begin
d[j]:=d[i]+a[k,2];
if not v[j] then begin
v[j]:=true; inc(t); q[t]:=j;
end;
end;
k:=a[k,0];
end;
v[i]:=false;
end;
end;
begin
readln(n,m);
for l:=1 to m do begin
readln(i,j,k);
inc(s); a[s,0]:=b[i];