Preface
本文单独发表于博客园，借鉴了 yyb 学长 的题解。
感觉是个很牛的题！
Solution
深刻地感受到了最短路算法的多变性，而不是单纯地作为一个模板存在。
发现路径的长度可以表示为如下一次函数的形式：\(y=kx+b\)，\(kx\) 表示经过的边给 \(x\) 乘上的系数，\(b\) 则表示经过的边的原本的权值之和（类似于普通最短路的 \(dist_x\)）。
考虑对于 \(b\) 先进行处理，最后叠加 \(kx\) 的贡献。朴素的 Bellman-Ford 转移是尝试对于整张图松弛 \(n\) 轮，每次找到合适的边进行松弛，如果超过 \(n-1\) 轮仍然能够松弛说明存在负环。即 \(dp_{i,j}\) 表示经过 \(i\) 条边，\(1\to j\) 的最短路，则有 \(dp_{i,u}+w\to dp_{i+1,v}\)。那么将这道题进行一些小改动：\(dp_{i,j,k}\) 表示经过了 \(i\) 条边，经过的系数为 \(k\)，\(1\to j\) 的最短路。那么实际上的路径长度为：\(dp_{i,j,k}+kx\)。
负环条件也很好判断了：如果 \(\min\{dp_{n,i,j}+jx\}\geq \min\{dp_{n-1,i,k}+kx\}\) 则存在负环，因为此时仍然可以从 \(n-1\) 松弛到 \(n\)。
那么解一下这个方程可以得到对于 \(i\) 来说的 \(x\) 构成负环的范围。求答案时对于每个点 \(i\)，如果想要其不存在负环，那么所有可达 \(i\) 的点 \(j\) 都不能有负环，所以对于所有 \(1\to j \to i\) 的点集 \(j\)，求 \(j\) 构成负环的区间的并集，则 \(1\to i\) 不存在负环的集合为该并集的补集。
具体实现细节很多啊。调的挺破防的。
Code
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=105,MAX=102,inf=1e18;
int n,m,dp[N][N][N<<2],f[N][N];
struct node{int u,v,val,typ;}e[N*N];
vector<pii>g[N],now;
signed main(){cin>>n>>m;for(int i=1,x,y,z,w;i<=m;i++){cin>>x>>y>>z>>w,f[x][y]=1;e[i]={x,y,z,w};}for(int i=1;i<=n;i++)f[i][i]=1;for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j]|=f[i][k]&f[k][j];for(int i=0;i<=n;++i)for(int j=1;j<=n;++j)for(int k=-n;k<=n;++k)dp[i][j][k+MAX]=inf;dp[0][1][MAX]=0;for(int i=1;i<=n;i++){memcpy(dp[i],dp[i-1],sizeof(dp[i]));for(int j=1;j<=m;j++){int u=e[j].u,v=e[j].v,val=e[j].val,typ=e[j].typ;for(int k=-n;k<=n;k++)if(dp[i-1][u][k+MAX]!=inf)dp[i][v][k+MAX+typ]=min(dp[i][v][k+MAX+typ],dp[i-1][u][k+MAX]+val);}}for(int i=1;i<=n;i++){for(int j=-n;j<=n;j++){if(dp[n][i][j+MAX]>=inf)continue;int L=-inf,R=inf,flg=0;for(int k=-n;k<=n;k++){if(dp[n-1][i][k+MAX]>=inf)continue;if(j>k)R=min(R,(int)ceil(1.0*(dp[n-1][i][k+MAX]-dp[n][i][j+MAX])/(j-k)));else if(j<k)L=max(L,(int)floor(1.0*(dp[n-1][i][k+MAX]-dp[n][i][j+MAX])/(j-k)));else if(dp[n][i][j+MAX]>=dp[n-1][i][k+MAX]){flg=1;break;}}if(!flg&&L<R)g[i].push_back({L,R});}}for(int i=1;i<=n;i++){now.clear();for(int j=1;j<=n;j++)if(f[1][j]&&f[j][i])for(auto it:g[j])now.push_back(it);sort(now.begin(),now.end());int L=inf,R=-inf,lst=-inf,flg=0;for(int j=0;j<now.size();j++){if(!j&&now[j].fi>-inf){L=-inf,R=now[j].fi,flg=1;break;}if(lst!=-inf&&lst<=now[j].fi){L=lst,R=now[j].fi,flg=1;break;}lst=max(lst,now[j].se);} if(!flg&&lst<inf)L=lst,R=inf;if(now.empty()||L==-inf||R==inf)cout<<"-1\n";else cout<<max(0ll,R-L+1)<<"\n";}return 0;
}