全WA求调
查看原帖
全WA求调
1056313
lihaoze2012楼主2024/8/24 10:50
#include<bits/stdc++.h>
using namespace std;
int n,m,s;
struct node{
	double v,w;
};
vector<node> g[100005];
double dis[100005],c;int A,B,a,b,vis[100005];
void dijkstra(int x){
	memset(dis,-0x3f,sizeof(dis));
	dis[x]=1;
	for(int i=1;i<=n;i++){
		int u=0;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&dis[j]>dis[u])
				u=j;
		}
		vis[u]=1;
		for(int k=0;k<g[u].size();k++){
			int v=g[u][k].v;
			int w=g[u][k].w;
			if(dis[v]<dis[u]*w){
				dis[v]=dis[u]*w;
			}
		}
	}
	return ;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>c;
		c=1.0*(100-c)/100.0;
		g[a].push_back(node{b,c});
		g[b].push_back(node{a,c});
	}
	cin>>A>>B;
	dijkstra(A);
	printf("%.8lf",100.0/dis[B]);
	return 0;
}
2024/8/24 10:50
加载中...