rt

dijkstra最短路O(n^2logn)过不了吗？

#include<bits/stdc++.h>
using namespace std;
int n,m,x1,y,x2,y2,u,v,w,adj[1510],cnt;
long long key[1510][1510];
bool book[1510],vis[1510];
long long ans;
struct edge
{
	int v,w,next;
}p[600010];
void build(int u,int v,int w,int i)
{
	p[i].v=v;
	p[i].w=w;
	p[i].next=adj[u];
	adj[u]=i;
	return;
}
struct dij
{
	int t,sum;
	bool operator < (const dij a)const{return sum>a.sum;}
};
priority_queue<dij> q;
void dijkstra(int k,int tag)
{
	q.push({k,0});
	while(!q.empty())
	{
		k=q.top().t;
		q.pop();
		if(book[k]) continue;
		book[k]=1;
		for(int i=adj[k];i;i=p[i].next)
		{
			if(key[tag][p[i].v]>key[tag][k]+p[i].w)
			{
				key[tag][p[i].v]=key[tag][k]+p[i].w;
				if(!book[p[i].v])q.push((dij){p[i].v,key[tag][p[i].v]});
			}
		}
	}
	return;
}
int main()
{
	cin >> n >> m >> x1 >>y >> x2 >> y2;
	for(int i=1;i<=m;i++)
	{
		cin >>u >>v >>w;
		build(u,v,w,i*2-1);
		build(v,u,w,i*2);
	}
	for(int i=1;i<=n;i++)
	{
		cnt=0;
		while(!q.empty()) q.pop();
		for(int j=1;j<=n;j++) vis[j]=0,book[j]=0,key[i][j]=LONG_LONG_MAX;
		key[i][i]=0;
		dijkstra(i,i);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
		//	cout<<i<<" "<<j<<" "<<key[x1][i]+key[i][j]+key[j][y]<<" "<<key[x1][y]<<" "<<key[x2][i]+key[i][j]+key[j][y2]<<" "<<key[x2][y2]<< endl;
			if(min(key[x1][i]+key[j][y],key[x1][j]+key[i][y])+key[i][j]==key[x1][y]&&min(key[x2][i]+key[j][y2],key[x2][j]+key[i][y2])+key[i][j]==key[x2][y2])
			{
				ans=max(ans,key[i][j]);
			}
		}
	}
	cout<<ans;
	return 0;
}