求助,输出inf,玄关
查看原帖
求助,输出inf,玄关
1125129
WJX120423楼主2024/5/14 13:53
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000+10;
int n,m,ss,t;
double dis[maxn];
bool vis[maxn];
struct node{
	int to;
	double w;
	node(int t,double ww){
		to=t; w=ww;
	}
};
vector<node> vec[maxn];
struct qnode{
	int id;
	double d;
	qnode(int i,double j){
		id=i; d=j;
	}
	bool friend operator <(qnode a,qnode b){
		return a.d<b.d;
	}
};
priority_queue<qnode> q;
int dij(int s){
	memset(dis,0.0,sizeof(dis));
	memset(vis,false,sizeof(vis));
	dis[s]=1.0; q.push(qnode(s,1.0));
	while(!q.empty()){
		int u=q.top().id; q.pop();
		if(vis[u]==true) continue;
		vis[u]=true;
		for(int i=0;i<vec[u].size();i++){
			int v=vec[u][i].to;
			if(dis[v]<dis[u]*vec[u][v].w){
				dis[v]=dis[u]*vec[u][v].w;
				cout<<u<<" "<<v<<" "<<dis[v]<<endl;
				if(!vis[v])q.push(qnode(v,dis[v]));
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		double w;
		cin>>u>>v>>w;
		vec[u].push_back(node(v,(100.0-w)/100.0));
		vec[v].push_back(node(u,(100.0-w)/100.0));
	}
	cin>>ss>>t;
	dij(ss);
	cout<<100.0/dis[t];
	return 0;
}
2024/5/14 13:53
加载中...