【codecomb2090】最小乘积路

2014年10月13日1,3280

题目描述

给定n个点的带权有向图,求从1到n的路径中边权之积最小的简单路径。

输入格式

第一行读入两个整数n,m,表示共n个点m条边。

接下来m行,每行三个正整数x,y,z,表示点x到点y有一条边权为z的边。

输出格式

输出仅包括一行,记为所求路径的边权之积,由于答案可能很大,因此输出它模9987的余数即可。

样例数据 1

输入

3 3
1 2 3
2 3 3
1 3 10

输出

9

备注

对于20%的数据,n<=10。

对于100%的数据,n<=1000,m<=1000000。边权不超过10000。

题解

边权相乘会爆,所以取对数变成相加

找到最短路后暴力算答案