0pts求助
  • 板块P1576 最小花费
  • 楼主KAqwq
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/7/14 19:11
  • 上次更新2023/11/3 09:50:09
查看原帖
0pts求助
448018
KAqwq楼主2023/7/14 19:11
#include<bits/stdc++.h>
typedef long long LL;
const int N=2e5+5,INF=1e9;
LL head[N],tail[N],nxt[N],tot;
double value[N];
inline void add_edge(LL u,LL v,double val){
	tail[++tot]=v;
	value[tot]=val;
	nxt[tot]=head[u];
	head[u]=tot;
}
LL n,m,A,B;
double dist[N];
bool vis[N];
inline void dijsktra(){
	for(LL i=1;i<=n;i++){
		LL maxn=-INF,num=0;
		for(LL j=1;j<=n;j++){
			if(!vis[j]&&dist[j]>maxn){
				num=j;
				maxn=dist[j];
			}
		}
		vis[num]=1;
		for(LL j=head[num];j;j=nxt[j]) dist[tail[j]]=std::max(dist[tail[j]],dist[num]*value[j]);
		if(!num) break;
	}
}
int main(){
	std::ios::sync_with_stdio(NULL);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	std::cin>>n>>m;
	while(m--){
		LL x,y;
		double v;
		std::cin>>x>>y>>v;
		add_edge(x,y,1-v/100);
		add_edge(y,x,1-v/100);
	}
	std::cin>>A>>B;
	for(LL i=1;i<=n;i++) dist[i]=-INF;
	dist[A]=1;
	dijsktra();
	std::cout<<std::fixed<<std::setprecision(8)<<100/dist[B];
	return 0;
}
2023/7/14 19:11
加载中...