月下无限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;
}
跪求大佬帮助