8个TLE的dij堆优化

#include<bits/stdc++.h>
using namespace std;
const int N=8000,M=800000;
int head[N],tot,n,m,vis[N];
double dis[N];
struct node{
	int v,next;
	double w;
}a[M];
priority_queue<pair<double,int>,vector<pair<double,int> >,greater<pair<double,int> > > q;
void add(int x,int y,double w){
	a[++tot].next=head[x];
	a[tot].v=y;
	a[tot].w=1.0-w/100.0;
	head[x]=tot;
}
void dijkstra(int x){
	dis[x]=1.0;
	vis[x]=1;
	q.push(make_pair(1.0,x));
	while(!q.empty()){
		int t=q.top().second;
		vis[t]=0;
		q.pop();
		for(int i=head[t];i!=-1;i=a[i].next){
			int v=a[i].v;double w=a[i].w;
			if(dis[v]<dis[t]*w){
				dis[v]=dis[t]*w;
				if(vis[v]==0){
					q.push(make_pair(dis[v],v));
					vis[v]=1;
				}
			}
		}
	}
}
signed main(){
	memset(dis,1000000000.0,sizeof(dis));
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		double w;
		scanf("%d%d%lf",&u,&v,&w);
		add(u,v,w);add(v,u,w);
	}
	int s,e;
	scanf("%d%d",&s,&e);
	dijkstra(s);
	double ans=100.0/dis[e];
	printf("%.8lf",ans);
	return 0;
}

AC的SPFA

#include<bits/stdc++.h>
using namespace std;
const int N=8000,M=800000;
int head[N],tot,n,m,vis[N];
double dis[N];
struct node{
	int v,next;
	double w;
}a[M];
queue<int> q;
void add(int x,int y,double w){
	a[++tot].next=head[x];
	a[tot].v=y;
	a[tot].w=1.0-w/100.0;
	head[x]=tot;
}
void dijkstra(int x){
	dis[x]=1.0;
	vis[x]=1;
	q.push(x);
	while(!q.empty()){
		int t=q.front();
		vis[t]=0;
		q.pop();
		for(int i=head[t];i!=-1;i=a[i].next){
			int v=a[i].v;double w=a[i].w;
			if(dis[v]<dis[t]*w){
				dis[v]=dis[t]*w;
				if(vis[v]==0){
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
}
signed main(){
	memset(dis,1000000000.0,sizeof(dis));
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		double w;
		scanf("%d%d%lf",&u,&v,&w);
		add(u,v,w);add(v,u,w);
	}
	int s,e;
	scanf("%d%d",&s,&e);
	dijkstra(s);
	double ans=100.0/dis[e];
	printf("%.8lf",ans);
	return 0;
}

十分疑惑