月下无限T

数据⑩怎么卡常出来？

我太难了QAQ

这里是链接

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
struct node{
	int to,nex,l,num;
};
node e[1008686];int head[500050],tot=0;
void push(int x,int y,int w,int ot){
	e[++tot].to=y;
	e[tot].nex=head[x];
	e[tot].l=w;
	e[tot].num=ot;
	head[x]=tot;
}
struct nade{
	int w,nm;
	bool operator< (const nade &n) const
	{
		return n.w<w;
	}
};
priority_queue<nade>q;
int n,m,d[1024],p[10086],num1=0,ans,sum=1;
bool b[1024];
int dij(int x){
	memset(d,0x3f3f3f3f,sizeof(d));
	memset(b,0,sizeof(b));
	d[1]=0;
	nade r;r.w=0;r.nm=1;
	q.push(r);
	while(q.size()){
		int f=q.top().nm;q.pop();
		b[f]=1;
		for(register int j=head[f];j;j=e[j].nex){
			int t=e[j].to;
			if(e[j].num==x)continue;
			if(d[t]>d[f]+e[j].l&&b[t]==0){
				d[t]=d[f]+e[j].l;
				if(!x)p[++num1]=e[j].num;
				r.nm=t,r.w=d[t];
				q.push(r);
			}
		}
	}
	return d[n];
}
int main()
{
	n=read(),m=read();
	int u,v,w;
	for(register int i=1;i<=m;i++){
		u=read(),v=read(),w=read();
		push(u,v,w,i);
		push(v,u,w,i);
	}
	ans=dij(0);
	for(register int i=1;i<=num1;i++){
		int p1=dij(p[i]);
		if(ans==p1)sum++;
		if(ans<p1){
			ans=p1;sum=1;
		} 
	}
	cout<<ans;
	return 0;
}

跪求大佬帮助