RE WA tle 爆零了 呜呜呜
  • 板块P1576 最小花费
  • 楼主homi
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/10/9 22:27
  • 上次更新2023/11/2 14:43:27
查看原帖
RE WA tle 爆零了 呜呜呜
944192
homi楼主2023/10/9 22:27
#include <bits/stdc++.h>
using namespace std;
#define MAXN 4005
#define inf -2147483647
int n,m,s,cnt,h[MAXN],to[MAXN],nxt[MAXN],a,b;
bool vis[MAXN];
double val[MAXN],dis[MAXN];
void add(int a,int b,double c)
{
	to[++cnt]=b;
	nxt[cnt]=h[a];
	val[cnt]=c;
	h[a]=cnt;
}
struct node
{
	int v;
	double w;
	friend bool operator <(node a,node b)
	{
		return a.w>b.w;
	}
}tmp;
priority_queue<node>q;
void Dijkstra()
{
	memset(dis,-0x3f,sizeof(dis));
	dis[a]=1;
	tmp.v=a,tmp.w=1;
	q.push(tmp);
	while(!q.empty())
	{
		int u=q.top().v;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=h[u];i;i=nxt[i])
		{
		    int v=to[i];
		    double l=val[i];
			if(!vis[v]&&dis[v]<dis[u]*l)
			{
				dis[v]=dis[u]*l;
                tmp.w=dis[v];
                tmp.v=v;
                q.push(tmp);
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		double w;
		scanf("%d%d%lf",&u,&v,&w);
		double k=1-w/100;
		add(u,v,k);
		add(v,u,k);
	}
	scanf("%d%d",&a,&b);
	Dijkstra();
    printf("%.8lf",100/dis[b]);
    return 0;
}

2023/10/9 22:27
加载中...