# [FZOJ1568]&&[2014-10-28 模拟赛] 时间与空间之旅 (tstrip.*)

7
3 2
1 2 100
2 3 99
3 2
1 2 100
2 3 98
2 1
1 2 1
3 2
1 2 1
3 2 1
3 2
1 2 -100000
2 3 -99999
3 3
1 2 2
2 3 2
3 1 -4
3 3
1 2 2
2 3 2
3 1 -5

1
0
0
-1
1
4
6

FZOJ 1568

## 代码 Code

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int inf=0x7fffffff/27.11;
int i,j,t,n,m,l,r,k,z,y,x;
int T,mid,cnt,ans;
struct edge
{
int to,next,val;
}e[10000];
bool used[105],b[105][105];
deque <int> q;
inline void ins(int u,int v,int w)
{
}
inline bool spfa(int s,int k)
{
int i,j,t,u,v,w;
memset(used,false,sizeof(used));
memset(inq,0,sizeof(inq));
for (i=1;i<=n;i++) dis[i]=inf;
while (!q.empty()) q.pop_front();
q.push_back(s);dis[s]=0;used[s]=true;inq[s]=1;
while (!q.empty())
{
u=q.front();q.pop_front();used[u]=false;
{
v=e[i].to;w=e[i].val+k;
if (dis[v]>dis[u]+w && b[v][n])
{
dis[v]=dis[u]+w;
if (!used[v])
{
inq[v]++;
if (inq[v]>n) return false;
used[v]=true;
if (!q.empty() && dis[v]<dis[q.front()]) q.push_front(v);
else q.push_back(v);
}
}
}

}
if (dis[n]>=inf || dis[n]<0) return false;
else return true;
}
int main()
{
scanf("%d",&T);
while (T--)
{
memset(b,false,sizeof(b));
ans=inf;l=-inf;r=inf;cnt=0;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
ins(x,y,z);
b[x][y]=true;
r=min(r,z);l=max(l,z);
}
for (i=1;i<=n;i++) b[i][i]=1;
for (k=1;k<=n;k++) for (i=1;i<=n;i++) for (j=1;j<=n;j++) b[i][j]=b[i][j] | b[i][k] & b[k][j];
r=max(-r,0);l=min(-l,0);
while (l<=r)
{
mid=(l+r)/2;
if (spfa(1,mid))
{
r=mid-1;
ans=min(ans,dis[n]);
}
else l=mid+1;
}
if (ans==inf) printf("-1\n");
else printf("%d\n",ans);
}
return 0;
}``````