社区讨论

为什么写挂了~~qwq

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

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@mi6x0b4f
此快照首次捕获于
2025/11/20 12:12
4 个月前
此快照最后确认于
2025/11/20 12:12
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define N 2050
using namespace std;
int n,m,a,b;
int head[N],now=0;
double dis[N];
bool vis[N];
struct wfq{
	int nxt,to;
	double v;
}bian[200050];
void Add(int x,int y,double z)
{
	bian[++now]= (wfq) {head[x], y, z}; 
	head[x]=now;
	return ;
}
struct cmp{
	bool operator()(int a,int b){
		return dis[a]>dis[b];
	}
};
priority_queue<int,vector<int>,cmp>q;
void dijkistra(int s)
{
	rep(i,1,n)dis[i]=-99999;dis[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.top();q.pop();
		vis[u]=1;
		for(int i=head[u];i;i=bian[i].nxt)
		{
			int z=bian[i].to;
			if(dis[z]<dis[u]*bian[i].v)
			dis[z]=dis[u]*bian[i].v;
			if(!vis[z])vis[z]=1,q.push(z);
		}
	}
}
int main()
{
	cin>>n>>m;
	rep(i,1,m)
	{
		int x,y;double v;
		scanf("%d%d%lf",&x,&y,&v);
		Add(x,y,1-v/100.0),Add(y,x,1-v/100.0);
	}
	cin>>a>>b;
	dijkistra(a);
	printf("%0.8lf",100.0/dis[b]);
	return 0;
}

回复

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

正在加载回复...