社区讨论

求条闭关,样例输出12点几

P1576最小花费参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mk962d42
此快照首次捕获于
2026/01/11 11:20
2 个月前
此快照最后确认于
2026/01/14 20:25
2 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=2026+10;
double dist[N];
int n,m,s,e;
vector<pair<int,int> > vec[N];
bool st[N];
void dijkstra()
{
	for(int i=1;i<=n;i++) dist[i]=0;
	dist[s]=1;
	priority_queue<pair<double,int>,vector<pair<double,int> >,greater<pair<double,int> > > heap;
	heap.push({1,s});
	while(heap.size())
	{
		auto t=heap.top();
		heap.pop();
		int ver=t.second;
		if(st[ver]==true) continue;
		st[ver]=true;
		for(auto p:vec[ver])
		{
			int j=p.first;
			if(dist[j]<dist[ver]+(1-1.0*p.second/100)*dist[ver])
			{
				dist[j]=dist[ver]+(1-1.0*p.second/100)*dist[ver];
				heap.push({dist[j],j});
			}
		}
	}
}
int main()
{
	
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		vec[u].push_back({v,w});
		vec[v].push_back({u,w});
	}
	cin>>s>>e;
	dijkstra();
	for(int i=1;i<=n;i++)
	{
		cout<<fixed<<setprecision(8)<<100/dist[e]<<endl;
	}
	cout<<fixed<<setprecision(8)<<100/dist[e];
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...