dijkstraWA求条
  • 板块P1576 最小花费
  • 楼主cgxd
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/21 16:22
  • 上次更新2024/8/21 16:22:25
查看原帖
dijkstraWA求条
1272259
cgxd楼主2024/8/21 16:22
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
#define double ld
int n, m, a, b;
double ans[2005];
bitset<2005> vis;
vector<int> to(1);
vector<double> dis(1);
vector<size_t> nxt(1);
size_t head[2005];
void add(int x, int y, double z){
	to.push_back(y), dis.push_back(z), nxt.push_back(head[x]);
	head[x] = to.size() - 1lu;
}multimap<double, int> mp;
double dijkstra(){
	mp.insert(pair<double, int>(1, a));
	while(mp.size()){
		int x = mp.begin() -> second;
		mp.erase(mp.begin());
		if(vis[x]) continue;
		vis[x] = 1;
		for(size_t i = head[x]; i; i = nxt[i]){
			int y = to[i];
			double d = dis[i];
			if(ans[y] < ans[x] * d)
				mp.insert(pair<double, int>(ans[y] = ans[x] * d, y));
		}
	}return 100 / ans[b];
}signed main(){
	scanf("%d%d", &n, &m);
	fill(ans, ans + n + 1, DBL_MIN);
	while(m--){
		int x, y;
		double z;
		scanf("%d%d%Lf", &x, &y, &z);
		add(x, y, 1 - z / 100);
		add(y, x, 1 - z / 100);
	}scanf("%d%d", &a, &b);
	ans[a] = 1;
	printf("%.8Lf", dijkstra());
	return 0;
}
2024/8/21 16:22
加载中...