样例已过,0pts求助,悬关,谢谢!
  • 板块P1576 最小花费
  • 楼主lcbridgeAK CSP-S
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/3/31 18:07
  • 上次更新2023/10/23 19:56:59
查看原帖
样例已过,0pts求助,悬关,谢谢!
546681
lcbridgeAK CSP-S楼主2023/3/31 18:07
#include <bits/stdc++.h>
using namespace std;
const int maxn=100000+5;
const int maxm=200000+5;
int n,m,s,t;
double dis[maxn];
struct edge{
	int to;
	double w;
};
vector <edge> g[maxm];
priority_queue <pair<double,int> > q;
bool vis[maxn];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v,z;
		scanf("%d%d%d",&u,&v,&z);
		double w=1.0-z/100.0;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	scanf("%d%d",&s,&t);
	dis[s]=1;
	q.push(make_pair(1,s));
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(int i=0;i<g[x].size();i++){
			int to=g[x][i].to;
			if(dis[to]<dis[x]*g[x][i].w){
				dis[to]=dis[x]*g[x][i].w;
				q.push(make_pair(-dis[to],to));
			}
		}
	}
	printf("%.8lf",100.0/dis[t]);
	return 0;
}  
2023/3/31 18:07
加载中...