2014年中山市选拔赛 dwarf tower
Time Limit:40000MS Memory Limit:65536K Total Submit:45 Accepted:18 Case Time Limit:1000MS
Description
Vasya在玩一个叫做"Dwarf Tower"的游戏，这个游戏中有n个不同的物品，它们的编号为1到n。现在Vasya想得到编号为1的物品。 获得一个物品有两种方式： 1. 直接购买该物品，第i件物品花费的钱为ci 2. 用两件其他物品合成所需的物品，一共有m种合成方式。 请帮助Vasya用最少的钱获得编号为1的物品。
Input
第一行有两个整数n,m(1<=n<=10000,0<=m<=100000)，分别表示有n种物品以及m种合成方式。 接下来一行有n个整数，第i个整数ci表示第i个物品的购买价格，其中0<=ci<=10^9。 接下来m行，每行3个整数ai,xi,yi，表示用物品xi和yi可以合成物品ai，其中(1<=ai,xi,yi<=n; ai<>xi, xi<>yi, yi<>ai)
Output
一行，一个整数表示获取物品1的最少花费。
Sample Input
5 3 5 0 1 2 5 5 2 3 4 2 3 1 4 5
Sample Output
2
Hint
数据范围 60%的数据，n<=100 100%的数据，n<=10000，m<=100000
Source
AC 100
思路：刚开始我居然想到了FloydT^T<蕾姆>,于是样例都没过……然后我想到用Forf,可是意外发现又不会写，完了，请教大佬把！Orz.
这题是这样的，我们可以根据条件数据创造一个图，边权有很多种，可以直接买（一条边），也可以换（另一边），另一边的情况要打邻接表（SPFA+邻接表~%/_/#@$$$?）便可以画一个图，然后枚举物品做最短路SPFA，输出对于1为终点的最短路即可。
var e:array[0..10005]of boolean; next,d,s,t,w,c,list:array[0..200005]of longint; n,i,j,m,x,y,a:longint; procedure spfa; var u,v,head,tail:longint; begin for u:=1 to n do begin head:=0; tail:=1; e[u]:=false; c[1]:=u; repeat inc(head); v:=list[c[head]]; while v>0 do begin if d[w[v]]+d[s[v]]<d[t[v]] then begin d[t[v]]:=d[w[v]]+d[s[v]]; if e[t[v]] then begin e[t[v]]:=false; inc(tail); c[tail]:=t[v]; end; end; v:=next[v]; end; e[c[head]]:=true; until head >= tail; end; end; begin fillchar(e,sizeof(e),false); read(n,m); for i:=1 to n do begin read(d[i]); e[i]:=true; end; readln; j:=1; for i:=1 to m do begin read(a,x,y); s[j]:=x; t[j]:=a; w[j]:=y; next[j]:=list[s[j]]; list[s[j]]:=j; inc(j); s[j]:=y; t[j]:=a; w[j]:=x; next[j]:=list[s[j]]; list[s[j]]:=j; inc(j); end; spfa; writeln(d[1]); end.
