Mn妹子求救[SPFA]样例过了但是过程出现很小的数,WA
查看原帖
Mn妹子求救[SPFA]样例过了但是过程出现很小的数,WA
228087
woshixingyu楼主2020/11/4 20:13
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;

struct node{
	int v;
	double dis;
	node(int _v,double _dis){
		v=_v;
		dis=_dis;
	}
};
vector<node>g[3000];
double d[3000];
bool vis[3000];

void SPFA(){
	queue<int>q;
	q.push(t);
	d[t]=1;
	vis[t]=true;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[s]=false;
		for(int i=0;i<g[x].size();i++){
			int v=g[x][i].v;
			double dis=g[x][i].dis;
			if(d[v]<d[x]*g[x][i].dis){
				d[v]=d[x]*g[x][i].dis;
				if(!vis[v]){
					q.push(v);
					vis[v]=true;
				}
			}
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		double dx;
		cin>>u>>v>>dx;
		double dis=1-dx/100;
		g[u].push_back(node(v,dis));
	}
	cin>>t>>s;
	for(int i=1;i<=n;i++){
		d[i]=0;
	}
	SPFA();
	if(d[s]<=1e-6)
		cout<<"sdaf"<<endl;
//	printf("%.8f",100/d[s]);	
	cout<<fixed<<setprecision(8)<<100/d[s]<<endl; 
	
	return 0;
	
}
2020/11/4 20:13
加载中...