小奇回地球

二分 最短路

题面

给一个有负边的$n$个点的图，如果能给全图边权同时加上（或减去）一个值$t$，问图中$1$到$n$的最短路距离非负时的最小距离。

• $T\leq10,n\leq100,-10^6\leq t\leq10^6$

解析

首先跑有负边图的最短路只能$SPFA$。

由于$t$和答案同增同减，具有单调性。我们可以二分$t$来取符合条件的最小距离。

问题出在对负环的处理上。
一开始想的是，有负环直接判不合法。
然而如果通过负环不能到达$n$号点，这个负环实际上可以忽略。
所以开头建反边，从$n$跑$dfs$看能到达哪些点，只对这些点跑最短路即可。
值得注意一下。
复杂度$O(Tn^2logt)$

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#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<int>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;
}