为什么样例过了但提交全是WA
查看原帖
为什么样例过了但提交全是WA
534025
gmllsswzw楼主2021/10/30 21:21
#include<bits/stdc++.h>
using namespace std;
int n,m,u,v,w,vis[2002],a,b;
double dis[2002],g[2002][2002]={},ans;
void Dijkstra(int u){
	memset(vis,0,sizeof(vis));
	vis[u]=1;
	for(int i=1;i<=n;i++)
		dis[i]=g[u][i];
	for(int t=1;t<=n;t++){
		int minn=0,temp;
		for(int i=1;i<=n;i++)
			if(!vis[i]&&dis[i]>minn){
				minn=dis[i];
				temp=i;
			}
			vis[temp]=1;
		for(int i=1;i<=n;i++)
			if(dis[i]<dis[temp]*g[temp][i])
				dis[i]=dis[temp]*g[temp][i];
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		g[u][v]=(100-w)*0.01;
		g[v][u]=(100-w)*0.01;
	}
	scanf("%d%d",&a,&b);
	for(int i=1;i<=n;i++)
		g[i][i]=1;
	Dijkstra(a);
	ans=100/dis[b];
	printf("%.8lf\n",ans);
	return 0;
}
2021/10/30 21:21
加载中...