题目背景
狗哥做烂了最短路，突然机智的考了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。
输入输出样例
输入样例#1：
3 3
1 2 3
2 3 3
1 3 10
输出样例#1：
9
说明
好好看一看再写哟w
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 2147483647
const ll INF = 0x3f3f3f3f3f3f3f3fll;
#define ri register int
template <class T> inline T min(T a, T b, T c)
{
return min(min(a, b), c);
}
template <class T> inline T max(T a, T b, T c)
{
return max(max(a, b), c);
}
template <class T> inline T min(T a, T b, T c, T d)
{
return min(min(a, b), min(c, d));
}
template <class T> inline T max(T a, T b, T c, T d)
{
return max(max(a, b), max(c, d));
}
#define pi acos(-1)
#define me(x, y) memset(x, y, sizeof(x));
#define For(i, a, b) for (int i = a; i <= b; i++)
#define FFor(i, a, b) for (int i = a; i >= b; i--)
#define mp make_pair
#define pb push_back
const int maxn = ;
#define mod 9987
const int N=; // name*******************************
int n,m;
struct edge
{
int to,next,w;
} e[N];
int Head[N];
int tot=;
int vis[N];
double dis[N];
int pre[N];
int val[N];
queue<int>que; // function******************************
void add(int u,int v,int w)
{
e[++tot].to=v;
e[tot].next=Head[u];
Head[u]=tot;
e[tot].w=w;
}
void spfa(int u)
{
que.push(u);
dis[u]=;
vis[u]=;
while(!que.empty())
{
int u=que.front();
vis[u]=;
que.pop();
for(int p=Head[u]; p; p=e[p].next)
{
int v=e[p].to;
int w=e[p].w;
if(dis[v]>dis[u]+log(w))
{
dis[v]=dis[u]+log(w);
pre[v]=u;
val[v]=w;
if(!vis[v])
{
vis[v]=;
que.push(v);
}
}
}
}
} //***************************************
int main()
{
// freopen("test.txt", "r", stdin);
int n,m;
cin>>n>>m;
For(i,,m)
{
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
For(i,,n)
dis[i]=inf;
spfa();
int i=n;
int ans=;
while(i!=)
{
ans=(ans*val[i]%mod)%mod;
i=pre[i];
}
cout<<ans;
return ;
}