P1576 反向 dijkstra 求调 qwq
  • 板块题目总版
  • 楼主KidA
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/1/26 17:36
  • 上次更新2024/1/26 20:14:45
查看原帖
P1576 反向 dijkstra 求调 qwq
542221
KidA楼主2024/1/26 17:36
#include<bits/stdc++.h>
using namespace std;

int n,m,a,b,ans;
double dis[2031];
bool vis[2031];
struct Edge{ int v; double w; };
struct Node{ 
	int u; double w;
	bool operator < (const Node &b) const{
		return w>b.w;
	} 
};
vector<Edge> G[200031];

void dijkstra(int s){
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++) dis[i]=2147483647.0;
	dis[s]=100.0;
	priority_queue<Node> pq; pq.push({s,100.0});
	while(!pq.empty()){
		Node now=pq.top(); pq.pop();
		if(vis[now.u]) continue; vis[now.u]=1;
		for(auto i:G[now.u]){
			if(dis[i.v]>dis[now.u]/i.w)
				dis[i.v]=dis[now.u]/i.w,pq.push({i.v,dis[i.v]});
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=1,u,v,w;i<=n;i++)
		cin>>u>>v>>w,G[u].push_back({v,1.0-w*0.01}),G[v].push_back({u,1.0-w*0.01});	
	cin>>a>>b;
	dijkstra(b),cout<<setprecision(8)<<fixed<<dis[a];
	return 0;
}
2024/1/26 17:36
加载中...