狗哥做烂了最短路，突然机智的考了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。
3 3 1 2 3 2 3 3 1 3 10
9
好好看一看再写哟w
#include <cstdio> #include <cstring> #include <iostream> #define maxn 1005 #define maxm 1000005 using namespace std; struct EdgeType { int v,e,w; }; struct EdgeType edge[maxm<<1]; int if_z,head[maxn],n,m,cnt; int dis[maxn],que[maxm<<2]; bool if_[maxn]; char Cget; inline void in(int &now) { now=0,if_z=1,Cget=getchar(); while(Cget>‘9‘||Cget<‘0‘) { if(Cget==‘-‘) if_z=-1; Cget=getchar(); } while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; Cget=getchar(); } now*=if_z; } int main() { in(n),in(m);int u,v,w; for(int i=1;i<=m;i++) { in(u),in(v),in(w); edge[++cnt].v=v,edge[cnt].w=w,edge[cnt].e=head[u],head[u]=cnt; } int h=0,tail=0; for(int i=1;i<=n;i++) dis[i]=0x7fffffff; que[tail++]=1,if_[1]=true,dis[1]=1; while(h<tail) { for(int i=head[que[h]];i;i=edge[i].e) { if(dis[edge[i].v]>dis[que[h]]*edge[i].w) { dis[edge[i].v]=dis[que[h]]*edge[i].w; if(!if_[edge[i].v]) if_[edge[i].v]=true,que[tail++]=edge[i].v; } } if_[que[h++]]=false; } cout<<dis[n]%9987; return 0; }
原文：http://www.cnblogs.com/chen74123/p/6680850.html