本文主要是介绍dwarf tower SSL_2516，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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为终点的最短路即可。
vare: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;
varu,v,head,tail:longint;
beginfor u:=1 to n dobeginhead:=0;tail:=1;e[u]:=false;c[1]:=u;
repeatinc(head);v:=list[c[head]];while v>0 do beginif d[w[v]]+d[s[v]]<d[t[v]] thenbegind[t[v]]:=d[w[v]]+d[s[v]];if e[t[v]] thenbegine[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 beginread(d[i]);e[i]:=true;end; readln;
j:=1;for i:=1 to m dobeginread(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.
这篇关于dwarf tower SSL_2516的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
