样例过了全WA求助
  • 板块P1576 最小花费
  • 楼主3a51_
  • 当前回复9
  • 已保存回复9
  • 发布时间2022/3/1 22:12
  • 上次更新2023/10/28 07:27:42
查看原帖
样例过了全WA求助
327444
3a51_楼主2022/3/1 22:12
/*
work by:Tothetime_tolife
time:1s
space:128MB
*/
#include<bits/stdc++.h>
#define int long long
#define Tothetime_tolife using
#define AK namespace
#define IOI std
Tothetime_tolife AK IOI;
const int Mod1=998244353;
const int Mod2=1000000007;
int gcd(int a,int b){return __gcd(a,b);}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qpow(int a,int b){int res=1;while(b){if(b&1){res=res*a%Mod1;}b>>=1;a=a*a%Mod1;}return res%Mod1;}
template <typename T> inline void read(T& x) {
	x=0;T f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=x*f;
	return;
}
template <typename T,typename ...Arg>void read(T& x,Arg& ...arg){
	read(x);
	read(arg...);
}
template <typename T>void write(T x) {
	if(x<0)putchar('-'),x=-x;
	if(x<10)putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}
template <typename T,typename ...Arg>void write(T& x,Arg& ...arg){
	write(x);
	putchar(' ');
	write(arg...);
}
const int N=2005;
const int M=100005;
const int Max=-2147483647;
int n,m,l,S,T,ans,cnt;
double x,y,z,t,Cnt=1;
double to[2*M],nxt[2*M],val[2*M],X[2*M],Y[2*M],Z[2*M],head[N],dis[N];
bool vis[N];
struct Node{
	int id;
    double w;
	friend bool operator<(const Node A,const Node B){
		return A.w>B.w;
	}
};
inline void add(int u,double v,double w){
	to[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
	val[cnt]=w;
	return;
}
priority_queue<Node> Q;
void dij(){
	memset(dis,0xaf,sizeof(dis));
	Node now;
	now.id=S;now.w=1.0;
	dis[S]=1.0;
	int p,ww;
	Q.push(now);
	while(!Q.empty()){
		Node x=Q.top();
		Q.pop();
		p=x.id;
		ww=x.w;
		if(vis[p] || dis[p]!=ww){
			continue;
		}
		vis[p]=1;
		int u;
		for(register int i=head[p];i;i=nxt[i]){
			u=to[i];
			if(dis[p]*val[i]>dis[u]){
				dis[u]=dis[p]*val[i];
				now.id=u;now.w=dis[u];
				Q.push(now);
			}
		}
	}
	return;
}
signed main()
{
	//;;;;;
	read(n,m);
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
        z=1-z/100.0;
		add(x,y,z);
		add(y,x,z);
	}
	read(S,T);
	dij();
	printf("%.8lf",100/dis[T]);
	return 0;
}
//QwQ

2022/3/1 22:12
加载中...