0pts,大佬求调qwq
查看原帖
0pts,大佬求调qwq
636358
WindyDay楼主2023/2/10 15:41
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int N = 2005;

struct node
{
	int v;
	double w;
	friend bool operator <(node a, node b)
	{
		return a.w < b.w;
	}
};

vector<node> g[N];
double dis[N];
bool vis[N];

int n, m;

void dijkstra(int st)
{
	priority_queue<node> q;
	memset(dis, -2e9, sizeof(dis));
	dis[st] = 1;
	q.push(node{st, 0});
	
	while(!q.empty())
	{
		node cur = q.top();
		q.pop();
		
		int u = cur.v;
		if(vis[u]) continue;
		
		vis[u] = 1;
		for(int i = 0; i < g[u].size(); i++)
		{
			int v = g[u][i].v;
			double w = g[u][i].w;
			if(!vis[v] && dis[v] < dis[u] * w)
			{
				dis[v] = dis[u] * w;
				q.push(node{v, dis[v]});
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int u, v;
		double w;
		cin >> u >> v >> w;
		w = (100 - w) / 100.0;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	int x, y;
	cin >> x >> y;
	dijkstra(x);
	cout << 100.0 / dis[y];
	return 0;
}
2023/2/10 15:41
加载中...