dijkstra好崩溃
查看原帖
dijkstra好崩溃
117192
无产者万岁楼主2020/7/24 13:50

求大佬改一下

#include <bits/stdc++.h>
using namespace std;
struct edge
{
	int v,next;
	double w;
}e[200001];
struct data
{
	double w;
	int now;
	bool operator<(const data &x)const
    {
        return x.w>w;
    }
};
int n,m,a,b,x,y,z,en,first[4001];
bool vis[200001];
double dis[4001];
void addedge(int x,int y,double z)
{
	en++;
	e[en].v=y;
	e[en].w=z;
	e[en].next=first[x];
    first[x]=en;
}
void Dijkstra()
{
	priority_queue<data> q;
	for(int i=1;i<=n;i++)
        dis[i]=0;
    dis[a]=1.0;
    q.push((data){1.0,a});
    while(!q.empty())
    {
    	data tmp=q.top();
    	q.pop();
    	int x=tmp.now;
    	if(vis[x])
			continue;
		vis[x]=1;
		for(int i=first[x];i;i=e[i].next)
		{
			int y=e[i].v;
			if(dis[y]<dis[x]*e[i].w)
			{  
				dis[y]=dis[x]*e[i].w;
				if(!vis[y])
					q.push((data){dis[y],y});
			}
		}
	}
}
int main()
{
	
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y>>z;
		addedge(x,y,(double)z/100);
		addedge(y,x,(double)z/100);
	}
	cin>>a>>b;
	Dijkstra();
	printf("%.8lf",100*1.0/dis[b]);
}
2020/7/24 13:50
加载中...