求助,输出 `inf`
查看原帖
求助,输出 `inf`
372780
Controls_Wishes楼主2021/8/2 19:45
#include<bits/stdc++.h>
#define re register int
using namespace std;
double d[2005];
vector<int>p[2005];
vector<double>a[2005];
bool f[2005];
priority_queue<pair<double,int>,vector<pair<double,int> >,less<pair<double,int> > >q;
int main(){
	int n,m,s,t,u,v;
	double w;
	scanf("%d%d",&n,&m);
	for(re i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		p[u].push_back(v),a[u].push_back(1-1.0*w/100);
	}
	scanf("%d%d",&s,&t);
	for(re i=1;i<=n;i++)
		if(i!=s)d[i]=-2147483647;
	q.push(make_pair(1,s));
	while(!q.empty()){
		u=q.top().second,q.pop();
		if(f[u])continue;
		f[u]=1;
		for(re i=0;i<p[u].size();i++){
			v=p[u][i],w=a[u][i];
			if(d[u]*w>d[v]){
				d[v]=d[u]*w; 
				if(!f[v])q.push(make_pair(d[v],v));
			}
		}
	}
	printf("%.8lf",100/d[t]);
	return 0;
}
2021/8/2 19:45
加载中...