【GDOI】【图论-最短路】时间与空间之旅

最近打的一场校内训练的某题原题。。。

题目如下：

Description

公元22××年，宇宙中最普遍的交通工具是spaceship。spaceship的出现使得星系之间的联系变得更为紧密，所以spaceship船长也成了最热门的职业之一。当然，要成为一名出色的船长，必须通过严格的考核，例如下面是最简单的问题中的一个。
用1~n的整数给n个星系标号，目前你在标号为1的星系，你需要送快递到标号为n的星系，星系之间由于存在陨石带，并不是都可以直连的。同时，由于超时空隧道的存在，在某些星系间飞行会出现时间静止甚至倒流，飞行时间为0或为负数。另外,由星系i到星系j的时间和由星系j到星系i的时间不一定是相同的。
在寄出日期之前收到快递被认为是不允许的，所以每部spaceship上都有一个速度调节装置，可以调节飞行的时间。简单来说其功能就是让所有两个星系间的飞行时间(如果可以直达)都增加或减少相同的整数值，你的任务就是调整速度调节器，找出一条用最短时间完成任务的路径，并且保证这个最短时间的值大于或等于0。

INPUT

输入文件包含多组数据，第1个数为T，表示数据的数量。
对于每一组数据，输入第1行为两个正整数N(≤N≤)，E(≤E≤N*(N-)/)，为星系的个数和星系间飞行的路线数。然后E行，每行三个整数i，j和t（≤i,j≤N，i≠j，-≤t≤)，表示由星系i到星系j飞行的时间为t。由i到j最多只会有一条飞行线路。

OUTPUT

输出文件共T行，每组数据输出一行；
如果可以通过调节速度调节器完成任务，则输出一个非负整数，表示由星系1到星系N的最短时间。
如果不能由星系1到达星系N，则输出-。

SAMPLEINPUT

  -

SAMPLEOUTPUT

HINT

样例说明

输入样例如图所示，其中节点标号表示相应星系，节点间数字表示所需时间。

如果设置速度控制器的值为0，则有如下路径:→→→→→……→→，使得投递的时间为负无穷大，显然是不符合要求的，所以应该把速度控制器的值设为1,相当于每个时间值加1,得到的最短路径为1→→→,所需时间为2+(-)+=。

--------------以下是题解-----------------------------

题意简析：题目就是给你一张有向图，你可以对图中所有边的边权加上或者减去一个整数，使得从1~n的最短路在非负的前提下最小。

解题思路：首先用floyd判断是否有解，然后二分答案用SPFAcheck是否有负环并求解，注意解的合法性即可。

附代码:

 #include<cstdio>
 #include<iostream>
 #include<cstring>
 #include<string>
 #include<algorithm>
 #include<map>
 #include<set>
 #include<vector>
 #include<cmath>
 #define For(i,a,b) for (int i=a; i<=b; i++)
 #define Ford(i,a,b) for (int i=a; i>=b; i--)
 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
 #define ll long long
 #define mod 1000000007
 #define INF 2000000000
 using namespace std;
 struct edge{
     int to,next,v;
 }e[];
 int head[];
 int rep[];
 int dist[];
 bool mrk[];
 int go[][];
 int q[];
 int T,n,m,l,r,cnt,ans;
 inline int in(){
     int x=,f=;
     char ch=getchar();
     while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
     while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
     return x*f;
 }

 inline void ins(int u,int v,int w)
 {
     e[++cnt].to=v;
     e[cnt].v=w;
     e[cnt].next=head[u];
     head[u]=cnt;
 }
 inline int check(int lim)
 {
     For(i,,n)mrk[i]=;
     For(i,,n)dist[i]=INF;
     For(i,,n)rep[i]=;
     memset(q,,sizeof(q));
     q[]=;mrk[]=;dist[]=;rep[]=;
     int t=,w=;
     while (t<w)
     {
         int now=q[++t];
         mrk[now]=;
         for (int i=head[now];i;i=e[i].next)
         {
           if (dist[e[i].to]>dist[now]+e[i].v+lim&&go[e[i].to][n])
           {
             dist[e[i].to]=dist[now]+e[i].v+lim;

             if (!mrk[e[i].to]&&rep[e[i].to]<=n)
             {
                 mrk[e[i].to]=;
                 rep[e[i].to]++;
                 if (rep[e[i].to]>n)return -;
                 q[++w]=e[i].to;
             }
           }
       }
     }
     return dist[n];
 }
 inline void doit()
 {
     mem(e,);
     mem(head,);
     mem(go,);
     cnt=;
     n=in(),m=in();
     int mn=INF;
     int mx=-INF;
     For(i,,m)
     {
         int x,y,z;
         x=in(),y=in(),z=in();
         ins(x,y,z);
         mn=min(mn,z);
         mx=max(mx,z);
         go[x][y]=;
     }
     For(i,,n)go[i][i]=;
     For(k,,n)
         For(i,,n)
             For(j,,n)
                 go[i][j]=go[i][j]|(go[i][k]&go[k][j]);
     if (!go[][n]){printf("-1\n");return;}
     l=-mx;r=-mn;
     ans=-;
     while (l<=r)
     {
         int mid=(l+r)>>,now=check(mid);
         if (now>=&&now!=INF){ans=now;r=mid-;}
         else l=mid+;
     }
     printf("%d\n",ans);
 }
 int main()
 {
     T=in();
     while (T--)doit();
 }

本文由Melacau编写，Melacau代表M星向您问好，如果您不是在我的博客http://www.cnblogs.com/Melacau上看到本文，请您向我联系，email:[e-mail].