题解 | #游游的正方形披萨#

想问下D题我这个spfa+二分为什么不对啊？大佬求助

using namespace std;
const int N=1e6+10;
const int inf=1e9;
#define int long long
#define fp(i,a,b) for(int i=a;i<=b;i++)
int n,m,hh;
int e[N],ne[N],h[N],w[N],d[N],idx;
int dis[N];
bool vis[N];
void add(int x,int y,int z,int t)
{
    e[idx]=y;
    ne[idx]=h[x];
    w[idx]=z;
    d[idx]=t;
    h[x]=idx++;
}
int spfa(int x)
{
    fp(i,1,n)vis[i]=0,dis[i]=inf;
    vis[1]=1;
    dis[1]=0;
    queue<int>q;
    q.push(1);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        vis[now]=0;
        for(int i=h[now];~i;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>dis[now]+d[i]&&w[i]>=x)
            {
                dis[j]=dis[now]+d[i];
                if(vis[j]==0)
                {
                    vis[j]=1;
                    q.push(j);
                }
            }
        }
    }
    return dis[n]<=hh;
}
signed main()
{

   memset(h,-1,sizeof h);

   cin>>n>>m>>hh;

   fp(i,1,m)
   {
       int x,y,z,t;
       cin>>x>>y>>z>>t;
       add(x,y,z,t);
       add(x,y,z,t);
   }

   int l=-1,r=1e9;  
   while(l<r)
   {
   	  int mid=(l+r+1)>>1;
   	  if(spfa(mid))l=mid;
   	  else r=mid-1;
   }
   cout<<l<<"\n";
   

    return 0;
}