题面
给一个有负边的\(n\)个点的图，如果能给全图边权同时加上（或减去）一个值\(t\)，问图中\(1\)到\(n\)的最短路距离非负时的最小距离。
\(T\leq10,n\leq100,-10^6\leq t\leq10^6\)
解析
首先跑有负边图的最短路只能\(SPFA\)。
由于\(t\)和答案同增同减，具有单调性。我们可以二分\(t\)来取符合条件的最小距离。
问题出在对负环的处理上。
一开始想的是，有负环直接判不合法。然而如果通过负环不能到达\(n\)号点，这个负环实际上可以忽略。 所以开头建反边，从\(n\)跑\(dfs\)看能到达哪些点，只对这些点跑最短路即可。 值得注意一下。 复杂度\(O(Tn^2logt)\)#include#include #include #include #include #include #include #define re register#define il inline#define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define fp(i,a,b) for(re int i=a;i<=b;i++)#define fq(i,a,b) for(re int i=a;i>=b;i--)using namespace std;const int mod=1e9+7,N=305;struct Edge{int to,nxt,w;}e[N*N];struct dat{int u,v,w;}a[N*N];int h[N],n,m,cnt,dis[N],mn,mx,num[N];bool vis[N],viss[N];queue Q;il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}il ll gi(){ re ll x=0,t=1; re char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') t=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*t;}il int SPFA(re int ysn){ fp(i,1,n) dis[i]=1e9,num[i]=0,vis[i]=0; while(!Q.empty()) Q.pop(); Q.push(1);vis[1]=1;dis[1]=0; while(!Q.empty()) { re int u=Q.front();Q.pop(); for(re int i=h[u];i+1;i=e[i].nxt) { re int v=e[i].to; if(!viss[v]) continue; if(dis[v]>dis[u]+e[i].w+ysn) { if((++num[v])>n) return -1e9; dis[v]=dis[u]+e[i].w+ysn; if(!vis[v]) vis[v]=1,Q.push(v); } } vis[u]=0; } return dis[n];}il void dfs(re int u){ viss[u]=1; for(re int i=h[u];i+1;i=e[i].nxt) { re int v=e[i].to; if(viss[v]) continue; dfs(v); }}int main(){ freopen("earth.in","r",stdin); freopen("earth.out","w",stdout); re int T=gi(); while(T--) { memset(h,-1,sizeof(h));cnt=0;mn=1e9;mx=-1e9; n=gi();m=gi(); fp(i,1,m) { a[i].u=gi(),a[i].v=gi(),a[i].w=gi();add(a[i].v,a[i].u,a[i].w); mn=min(mn,a[i].w);mx=max(mx,a[i].w); } dfs(n); memset(h,-1,sizeof(h));cnt=0; fp(i,1,m) add(a[i].u,a[i].v,a[i].w); if(SPFA(-mn+100)==1e9) {puts("-1");continue;} re int l=-mx,r=-mn,ans=0; while(l<=r) { re int mid=l+r>>1,zsy=SPFA(mid); if(zsy>=0) ans=zsy,r=mid-1; else l=mid+1; } printf("%d\n",ans); } fclose(stdin); fclose(stdout); return 0;}