~~因为最短路在呐喊:哇!!!~~
by Collide @ 2020-03-14 13:37:00
现在学术贴都没人回的吗
by zhoukangyang @ 2020-03-14 13:46:46
@[zhoukangyang](/user/173660) 试试看在松弛那个地方加log
别在加边的地方加
试试看,说不定过了
by Lice @ 2020-03-14 13:48:33
@[_Wallace_](/user/61430) orz,我试试看
by zhoukangyang @ 2020-03-14 13:49:23
@[_Wallace_](/user/61430) 等等,为什么要加log
by zhoukangyang @ 2020-03-14 13:51:07
@[zhoukangyang](/user/173660) 就是说把加边那个不要直接算log,松弛时直接算
by Lice @ 2020-03-14 13:52:33
WA
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,qaq[100001],p,mis;
double s[100001],minn;
int head[100001],last[100001];
struct node {
int next,to,we;
} q[1000001];
void add(int start_,int end_,int weight,int bh) {
if(head[start_]==0) head[start_]=bh;
else q[last[start_]].next=bh;
last[start_]=bh,q[bh].to=end_,q[bh].we=weight;
}
int main() {
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) s[i]=qaq[i]=2147483647.0;
s[1]=0,qaq[1]=1,p=n;
for(int i = 1; i <= m; i++) {
int XXX,YYY,ZZZ;
scanf("%d%d%d",&XXX,&YYY,&ZZZ);
add(XXX,YYY,ZZZ,i);
}
while(p) {
--p;
minn=2147483647.0;
for(int i = 1; i <= n; i++) if(s[i]<minn) minn=s[i],mis=i;
if(minn>2000000000.0) continue;
for(int i = head[mis]; i != 0; i = q[i].next)
if(minn+log(double(q[i].we))<s[q[i].to])
s[q[i].to]=minn+log(double(q[i].we)),qaq[q[i].to]=qaq[mis]*q[i].we%9987;
s[mis]=2147483647.0;
}
printf("%d",qaq[n]);
return 0;
}
```
by zhoukangyang @ 2020-03-14 13:56:16
松弛的时候再log不然会可能会报精度
by RedreamMer @ 2020-03-14 13:57:10
还有,不需要强制转换double
by RedreamMer @ 2020-03-14 13:57:51
呃,但我是这样过的啊
by Lice @ 2020-03-14 13:57:57