提问
  • 板块P1576 最小花费
  • 楼主xuyian
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/9/18 21:41
  • 上次更新2024/9/19 12:21:49
查看原帖
提问
1290709
xuyian楼主2024/9/18 21:41

这道题求的不是最长路吗
那为什么我把dis初始值设为0x3f而不是-0x3f能过
代码:

#include<bits/stdc++.h>
#define re register
#define il inline
using namespace std;
typedef pair<int ,double > pii;
vector<pii> G[2005];
double dis[2005];
priority_queue<pii ,vector<pii> ,greater<pii> > q;
int n,m;
int u,v,a,b;
double c;
int main(){
	cin>>n>>m;
	for (re int i=1;i<=m;i++){
		cin>>u>>v>>c;
		G[u].push_back({v,1-c/100});
		G[v].push_back({u,1-c/100});
	}
	cin>>a>>b;
	memset(dis,0x3f,sizeof dis);
	dis[a]=1;
	q.push({a,1});
	while (!q.empty()){
		int u=q.top().first;
		c=q.top().second;
		q.pop();
		for (pii &p:G[u])
			if (dis[p.first]<dis[u]*p.second){
				q.push({p.first,dis[p.first]});
				dis[p.first]=dis[u]*p.second;
			}
	}
	printf("%.8lf",100.0/dis[b]);
	return 0;
}```
2024/9/18 21:41
加载中...