lz样例都没过,交了一发竟然过了,答案让保留八位,但我的从第二位小数开始就与样例有差
所以是数据水还是评测方式的问题?
代码如下
#warning By KonjAC_xrs
#warning ( testing == 0 ) ? Yes : No
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
using namespace std;
inline ll read()
{
ll x=0,f=1; char ch=getchar();
while (!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while ( isdigit(ch)) {x = x * 10+ch-48; ch=getchar();}
return x*f;
}
inline void xrs(ll x)
{
if(x<0) putchar('-') , x=-x;
if(x>9) xrs(x/10);
putchar(x%10+'0');
}
const ll inf=1e17;
//const ll mod=;
const ll nore=2e5+20;
ll n,m;
ll pre[nore],ok[nore];
ll tot,ver[nore<<1],head[nore],edge[nore<<1],nxt[nore<<1];
inline void add(ll x,ll y,ll z)
{
ver[++tot]=y;
edge[tot]=z;
nxt[tot]=head[x];
head[x]=tot;
}
ll d[nore];
bool vis[nore];
inline void dij(ll s)
{
for(register ll i=1;i<=n;i++)
d[i]=inf , vis[i]=0;
priority_queue < pair < ll , ll > > q;
d[s]=0;
q.push(make_pair(0,s));
while(!q.empty())
{
ll x=q.top().second;
q.pop();
if(vis[x]) continue;
vis[x]=1;
for(register ll i=head[x];i;i=nxt[i])
{
ll y=ver[i]; ll z=edge[i];
if(d[y]>d[x]+z)
{
d[y]=d[x]+z;
pre[y]=x;
ok[y]=z;
q.push(make_pair(-d[y],y));
}
}
}
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=read(); m=read();
for(register ll i=1;i<=m;i++)
{
ll u=read(); ll v=read(); ll z=read();
add(u,v,z); add(v,u,z);
}
ll a=read(); ll b=read();
dij(a);
ll tmp=b;
double ans=100.0;
// puts("");
// xrs(pre[tmp]);
// puts("");
while(pre[tmp]!=a)
{
ans/=(double)(1-(double)ok[tmp]*0.01);
tmp=pre[tmp];
}
ans/=(double)(1-(double)ok[tmp]*0.01);
printf("%.8f",ans);
getchar();
return 0;
}
/*
a*(1-z*0.01)=b ,
b/(1-z*0.01)=a ;
*/
My ans is
103.09278351
The yangli is
103.07153164