$$O(n^3)\ \text{用}floyd\ \ \ orz\ \ \ sto$$
by disangan233 @ 2019-01-12 14:13:51
因为这题正解是边权取对数然后跑dijkstra
by NaCly_Fish @ 2019-01-12 14:14:04
@[OneRepublic](/space/show?uid=78546)
## $$n\leq 10^3$$
by disangan233 @ 2019-01-12 14:14:35
@[NaCly_Fish](/space/show?uid=115864) orz
by disangan233 @ 2019-01-12 14:14:49
你没有2wa8t就应该感谢上帝
by star_city @ 2019-01-12 14:15:19
@[NaCly_Fish](/space/show?uid=115864) tql%%%
~~如果有负权怎么做~~
by SSerxhs @ 2019-01-12 14:15:43
乘法负权orz
~~教教本蒟蒻吧~~
by star_city @ 2019-01-12 14:17:09
@[SSerxhs](/space/show?uid=29826) 怎么可能呢
by OneRepublic @ 2019-01-12 14:26:03
```cpp
#include<bits/stdc++.h>
using namespace std;
long long road[1001],mmp[1001][1001];
int n,m;
bool book[1001];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
mmp[i][j]=0xffffff;
}
road[i]=0xffffff;
book[i]=0;
}
for(int i=1;i<=n;i++){
int x,y,z;
cin>>x>>y>>z;
mmp[x][y]=z;
}
for(int i=1;i<=n;i++){
road[i]=mmp[1][i];
}
book[1]=1;road[1]=0;
for(int i=1;i<=n;i++){
long long MIN=0xffffff;int k=0;
for(int j=1;j<=n;j++){
if(MIN>road[j]&&book[j]==false){
MIN=road[j];k=j;
}
}
if(k==0) break;
book[k]=1;
for(int v=1;v<=n;v++){
if(mmp[k][v]!=0xffffff){
if(road[v]>road[k]*mmp[k][v]) road[v]=road[k]*mmp[k][v];
}
}
}
cout<<road[n]%9987;
return 0;
}
```
by OneRepublic @ 2019-01-12 14:26:33
@[SSerxhs](/space/show?uid=29826) 如果有负权，且有环，那就是无解。。否则就跑最长路
by NaCly_Fish @ 2019-01-12 14:26:42