求助样例过了0pts
  • 板块P1576 最小花费
  • 楼主粉丝
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/4/6 12:03
  • 上次更新2023/10/23 19:17:11
查看原帖
求助样例过了0pts
127935
粉丝楼主2023/4/6 12:03

能用pair吗

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
int tot;
int v[2000005],nxt[2000005],head[2000005],vis[2000005];
double w[2000005],dist[2000005];
void add_edge(int x,int y,double val)
{
	v[++tot]=y;w[tot]=val;
	nxt[tot]=head[x];head[x]=tot;
}
void dijkstra(int x)
{
	memset(dist,0,sizeof(dist));
	memset(vis,0,sizeof(vis));
	dist[x]=1;
	priority_queue<pair<int,double> > q;
	q.push(make_pair(x,1));
	while(!q.empty())
	{
		int u=q.top().first;
		q.pop();
		if(vis[u]==1) continue;
		vis[u]=1;
		for(int i=head[u];i;i=nxt[i])
		{
			if(dist[v[i]]<dist[u]*w[i])
			{
				dist[v[i]]=dist[u]*w[i];
				if(!vis[v[i]]) q.push(make_pair(v[i],dist[v[i]]));
			}
		}
	}
}
int main()
{
	//freopen("P1576.in.txt","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;double c;
		cin>>a>>b>>c;
		//cout<<double(100-c)/(100)<<endl;
		add_edge(a,b,1-c/100);
		add_edge(b,a,1-c/100);
	}
	cin>>s>>t;
	dijkstra(s);
	printf("%.8lf",100.0/dist[t]); 
	return 0;
}
2023/4/6 12:03
加载中...