样例未过求调
查看原帖
样例未过求调
605945
luo_xiaoran楼主2023/4/21 14:19
#include<bits/stdc++.h>
using namespace std;
int cnt,n,m,s,t,b,head[100010];
double dis[100010];
bool vis[100010];
struct edge{
	int to,next;
	double dis;
}e[500010];
struct node{
	int pos;
	double dis;
	bool operator <(const node &x)const{
		return x.dis<dis;
	}
};
priority_queue<node> q;
void dijkstra(){
	dis[s]=1.0;
	q.push((node){s,1.0});
	while(!q.empty()){
		node tmp=q.top();
		q.pop();
		int x=tmp.pos;
		double d=tmp.dis;
		if(vis[x])
			continue;
		vis[x]=1;
		for(int i=head[x];i;i=e[i].next){
			int y=e[i].to;
			if(dis[y]>dis[x]*e[i].dis){
				dis[y]=dis[x]*e[i].dis;
				if(!vis[y])
					q.push((node){dis[y],y});
			}
		}
	}
}
void add(int u,int v,double d){
	e[++cnt].dis=d;
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		dis[i]=1.0*0x7fffff;
	for(int u,v,i=1;i<=m;i++){
		double d;
		scanf("%d%d%lf",&u,&v,&d);
		d=100.0/(100.0-d);
		add(u,v,d);
		add(v,u,d);
	}
	scanf("%d%d",&s,&t);
	dijkstra();
	printf("%.8lf",100.0*dis[t]);
	return 0;
}
2023/4/21 14:19
加载中...