题目：
题目背景
狗哥做烂了最短路，突然机智的考了Bosh一道，没想到把Bosh考住了…你能帮Bosh解决吗？
他会给你100000000000000000000000000000000000%10金币w
题目描述
给定n个点的带权有向图，求从1到n的路径中边权之积最小的简单路径。
输入输出格式
输入格式： 第一行读入两个整数n，m，表示共n个点m条边。 接下来m行，每行三个正整数x，y，z，表示点x到点y有一条边权为z的边。
输出格式： 输出仅包括一行，记为所求路径的边权之积，由于答案可能很大，因此狗哥仁慈地让你输出它模9987的余数即可。
废话当然是一个数了w
//谢fyszzhouzj指正w
对于20%的数据，n<=10。
对于100%的数据，n<=1000，m<=1000000。边权不超过10000。
作者思路：显然，用最短路。 先找出最值路径，再搜最短路。 注意要赋初始值10001。
代码：
uses math;var a:array[0..1001,0..1001] of longint; f:array[0..1001] of longint; n,m:longint;PRocedure init;var x,y,z,i,j:longint;begin read(n,m); for i:=1 to n do for j:=1 to n do if i<>j then a[i,j]:=10001; for i:=1 to m do begin read(x,y,z); a[x,y]:=min(a[x,y],z); end; for i:=1 to n do f[i]:=10001;end;procedure short;var b:array[0..1001] of boolean; i,j,k,xmin:longint;begin fillchar(b,sizeof(b),false); for i:=1 to n do f[i]:=a[1,i]; b[1]:=true; for i:=1 to n-1 do begin xmin:=maxlongint; k:=0; for j:=1 to n do if not(b[j]) then begin xmin:=min(f[j],xmin); k:=j; end; b[k]:=true; if k=0 then break; for j:=1 to n do if not(b[j]) then f[j]:=min(f[j],a[k,j]*f[k]mod 9987); end;end;begin init; short; write(f[n]);end.新闻热点
疑难解答
