描述 Description
公元 22×× 年，宇宙中最普遍的交通工具是 spaceship。spaceship 的出现使得星系之间的联系变得更为紧密，所以 spaceship 船长也成了最热门的职业之一。当然，要成为一名出色的船长，必须通过严格的考核，例如下面是最简单的问题中的一个。
用 1~n 的整数给 n 个星系标号，目前你在标号为 1 的星系，你需要送快递到标号为 n 的星系，星系之间由于存在陨石带，并不是都可以直连的。同时，由于超时空隧道的存在，在某些星系间飞行会出现时间静止甚至倒流，飞行时间为 0 或为负数。另外, 由星系 i 到星系 j 的时间和由星系 j 到星系 i 的时间不一定是相同的。
在寄出日期之前收到快递被认为是不允许的，所以每部 spaceship 上都有一个速度调节装置，可以调节飞行的时间。简单来说其功能就是让所有两个星系间的飞行时间 (如果可以直达) 都增加或减少相同的整数值，你的任务就是调整速度调节器，找出一条用最短时间完成任务的路径，并且保证这个最短时间的值大于或等于 0。
输入格式 InputFormat
输入文件包含多组数据，第 1 个数为 T，表示数据的数量。
对于每一组数据，输入第 1 行为两个正整数 N(2≤N≤100)，E(1≤E≤N*(N-1)/2)，为星系的个数和星系间飞行的路线数。然后 E 行，每行三个整数 i，j 和 t（1≤i,j≤N，i≠j，-100000≤t≤100000)，表示由星系 i 到星系 j 飞行的时间为 t。由 i 到 j 最多只会有一条飞行线路。
输出格式 OutputFormat
输出文件共 T 行，每组数据输出一行；
如果可以通过调节速度调节器完成任务，则输出一个非负整数，表示由星系 1 到星系 N 的最短时间。
如果不能由星系 1 到达星系 N，则输出 - 1。
样例输入 SampleInput
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
样例输出 SampleOutput
1
0
0
-1
1
4
6
代码 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];
int head[105],dis[105],inq[105];
bool used[105],b[105][105];
deque <int> q;
inline void ins(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].next=head[u];e[cnt].val=w;
head[u]=cnt;
}
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;
for (i=head[u];i;i=e[i].next)
{
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(head,0,sizeof(head));
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;
}