求条P1576 80pts
  • 板块灌水区
  • 楼主封禁用户
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/7 22:07
  • 上次更新2025/1/8 16:09:30
查看原帖
求条P1576 80pts
741674
封禁用户楼主2025/1/7 22:07
#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<bitset>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<new>
#include<set>
#define int long long
#define double long double
#define inf 0x3f3f3f3f
#define N 100005
#define N2 105
#define N3 1005
#define N4 10005
const int E = 1e9;
using namespace std;
vector<pair<int, int> >a[N];
double t[N];
bool st[N];
void dijkstra(int sss)
{
	t[sss] = 1;
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >q;
	q.push({ 1, sss });
	while (!q.empty())
	{
		auto x = q.top();
		q.pop();
		int ver = x.second;
		if (st[ver])continue;
		st[ver] = 1;
		for (auto& i : a[ver])
		{
			int j = i.first;
			int w = i.second;
			if (t[j] > t[ver] / (1 - 0.01 * w))
			{
				t[j] = t[ver] / (1 - 0.01 * w);
				q.push({ t[j],j });
			}
		}
	}
}
signed main()
{
	int n, m;
	cin >> n >> m;
	int i;
	for (i = 0; i <= n; i++)
	{
		t[i] = 100000000;
	}
	for (i = 0; i < m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		a[u].push_back({ v,w });
		a[v].push_back({ u,w });
	}
	int xx, b;
	cin >> xx >> b;
	dijkstra(xx);
	cout << fixed<< setprecision(8)<<t[b]*100;
}
2025/1/7 22:07
加载中...