RT，T#16，人调麻了

#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long op,s,t,l;
long long head[5005],nxt[20005],targetx[20005],targetw[20005],targetk[20005],pre[5005],tot;
long long mp[5005][5005];
bool vis[5005];
bool vis1[5005];
long long dis[5005],cnt[5005];
queue<long long> q;
int dfs(int x,int sum){
	if(vis1[x]) return sum;
	vis1[x]=1;
	return dfs(pre[x],sum+mp[pre[x]][x]); 
}
void add(long long x,long long y,long long w,long long k){
	tot++;
	nxt[tot]=head[x];
	head[x]=tot;
	targetx[tot]=y;
	targetw[tot]=w;
	targetk[tot]=k;
	mp[x][y]=k;
}
long long check(long long mid){
	for(long long i=1;i<=n;i++){
		dis[i]=1e17+10;
	}
	while(q.size()) q.pop();
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	memset(pre,0,sizeof(pre));
	dis[1]=0;
	vis[1]=1;
	q.push(1);
	cnt[1]=1;
	while(q.size()){
		long long x=q.front();
		q.pop();
		vis[x]=0;
		for(long long i=head[x];i;i=nxt[i]){
			long long y=targetx[i],w=targetw[i],k=targetk[i];
			if(dis[x]+k*mid+w<dis[y]){
				dis[y]=dis[x]+k*mid+w;
				pre[y]=x;
				if(vis[y]) continue;
				vis[y]=1;
				q.push(y);
				if(++cnt[y]>n){
					memset(vis1,0,sizeof(vis1));
					int sum=dfs(y,0);
					if(sum>0) return 1;
					else return -1;
		        }
			}
		}
	} 
	return 0;
}
long long findr(long long l,long long r){
	if(l==r) return l;
	long long mid=(l+r+1)>>1;
	long long tp=check(mid);
	if(tp==1){
		return findr(mid+1,r);
	}else if(tp==-1){
		return findr(l,mid-1);
	}else{
		return findr(mid,r);
	}
}
long long findl(long long l,long long r){
	if(l==r) return l;
	long long mid=(l+r)>>1;
	long long tp=check(mid);
	if(tp==1){
		return findl(mid+1,r);
	}else if(tp==-1){
		return findl(l,mid-1);
	}else{
		return findl(l,mid);
	}
}
int main(){
	cin>>n>>m;
	for(long long i=1;i<=n-1;i++){
		add(i+1,i,-1,0);
	}
	add(1,n,-1,1);
	for(long long i=1;i<=m;i++){
		cin>>op>>s>>t>>l;
		if(op==1){
			if(s<t){
				add(t,s,-l,0);
			}else{
				add(t,s,-l,1);
			}
		}else{
			if(s<t){
				add(s,t,l,0);
			}else{
				add(s,t,l,-1);
			}
		}
	}
	long long r=findr(0,1e12),l=findl(0,1e12);
	if(r==1e12){
		cout<<-1;
	}else{
		cout<<r-l+1;
	}
	return 0;
}