题目背景
狗哥做烂了最短路，突然机智的考了Bosh一道，没想到把Bosh考住了…你能帮Bosh解决吗？
他会给你100000000000000000000000000000000000 %10 金币（滑稽）
题目描述
给定n个点的带权有向图，求从1到n的路径中边权之积最小的简单路径。
输入输出格式
输入格式：
第一行读入两个整数n，m，表示共n个点m条边。 接下来m行，每行三个正整数x，y，z，表示点x到点y有一条边权为z的边。
输出格式：
输出仅包括一行，记为所求路径的边权之积，由于答案可能很大，因此狗哥仁慈地让你输出它模9987的余数即可。
对于20%的数据，n<=10。
对于100%的数据，n<=1000，m<=1000000。边权不超过10000。
输入输出样例
输入样例#1:
3 3
1 2 3
2 3 3
1 3 10
输出样例#1:
9
（这题数据好水，本来以为要爆ll，可是直接过了）
思路：n<=1000，一看到数据就觉得要用Dijkstra，而且邻接矩阵也足够存边了。
注意：1.初始化：边无穷大（0x7fffffff），最短路径fi是从1到i的边的权值，判白点的数组bi=0。
2.更新的时候，要判边是否连通，不然乘了之后有可能会爆回负数，结果就错了。
3.过程中不用mod，也不能mod（想一想，为什么），最后再mod。
P.S.本来觉得过不了，没想到过了^_^
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
int edge[1001][1001];//邻接矩阵
ll f[1001];//单源最短路
int b[1001];//标记白点
int main(){
cin>>n>>m;
//初始化
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
edge[i][j]=0x7fffffff;
}
f[i]=0xfffffff;
b[i]=0;
}
//输入
for(int i=1;i<=n;i++){
int x,y,v;
cin>>x>>y>>v;
edge[x][y]=v;
}
//初始化
for(int i=1;i<=n;i++){
f[i]=edge[1][i];
}
f[1]=0;//起点到起点的最短路是0
b[1]=1;//标记成白点
for(int i=1;i<=n;i++){
int mn=0x7fffffff;
int k=0;
for(int j=1;j<=n;j++){
if((!b[j])&&(f[j]<mn)){//如果不是白点，而且是目前最短的
mn=f[j];
k=j;
}
}
if(k==0)break;//无法更新，退出
b[k]=1;//标记白点
//更新所有点
for(int j=1;j<=n;j++){
if((edge[k][j]!=0x7fffffff)&&(f[j]>f[k]*edge[k][j])){
f[j]=f[k]*edge[k][j];
}
}
}
cout<<f[n]%9987;//记得取模
return 0;
}