堆优化dj,好像数据有溢出,求改。
查看原帖
堆优化dj,好像数据有溢出,求改。
181715
gjh303987897楼主2022/2/24 23:07
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
priority_queue<pair<int,int> >q;
const int maxn=1e5+5;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>='9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int n,m,a,dist[maxn],vis[maxn],b;
struct data{
	int to;
	int next;
	int w;
}t[maxn];
int js,head[maxn];
inline void add(int u,int v,int w){
	t[++js].next=head[u]; t[js].to=v; t[js].w=w; head[u]=js;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z); add(y,x,z);
	}
	cin>>a>>b;
	for(int i=1;i<=n;i++) dist[i]=1e8+5;
	vis[a]=1; q.push(make_pair(0,a));
	while(q.size()){
		int x=q.top().second; q.pop();
		if(vis[x]) continue; 
		vis[x]=1;
		for(int i=head[x];i;i=t[i].next){
			int edge=t[i].to;
			if(t[i].w+dist[x]<dist[edge]){
				dist[edge]=t[i].w+dist[x];
				q.push(make_pair(-dist[edge],edge));
			}
		}
	}
	double ans=10000/dist[b]*-1;
	cout<<ans;
	return 0;
} 
2022/2/24 23:07
加载中...