原题目名：时间与空间之旅

2015.9.13日hzwer重制了题面与数据

「题目背景」

开学了，小奇在回地球的路上，遇到了一个棘手的问题。

「问题描述」

简单来说，它要从标号为1的星球到标号为n的星球，某一些星球之间有航线。由于超时空隧道的存在，从一个星球到另一个星球时间可能会倒流，而且，从星球a到b耗费的时间和星球b到a耗费的时间不一定相同。

宇宙法规定：“禁止在出发时间前到达目的地。”

每艘飞船上都有速度调节装置，可以调节飞行的时间。其功能可以使得整次航程中所有两星球间的飞行时间增加或减少相同的整数值。你的任务是帮助它调整速度调节器，找出一条最短时间到达目的地的路径。

「输入格式」

输入文件包含多组数据，第1个数为T，表示数据组数。

对于每组数据，输入第1行为两个正整数n，m，为星球的个数和星球间的路线数。接下来m行，每行三个整数i，j和t，表示由星球i到星球j飞行的时间为t。由i到j最多只会有一条飞行线路。

「输出格式」

输出文件共T行，每组数据输出一行。

如果可以通过调节速度调节器完成任务，则输出一个非负整数，表示由星球1到星球n的最短时间。（注意最短时间要大于或者等于0）。

如果不能由星球1到达星球n，则输出-1。

「样例输入」

1

4 5

1 2 1

1 3 1

2 3 -3

3 1 1

3 4 1

「样例输出」

2

「样例解释」

把速度控制器的值设为1,相当于每个时间值加1,得到的最短路径为1→2→3→4,所需时间为2+(-2)+2=2。

「数据范围」

1，2号测试点，保证所有星球出度不超过1

3，4号测试点，n<=10

5，6号测试点，-100<=t<=100

对于100%的数据T<=10，n<=100，m<=n*(n-1)，-100000<=t<=100000

数据随机和构造结合生成

题解

题意是将有向图的所有边权加上一个值，使得1-n的最短路大于等于0且尽量小

1，2号测试点是n元环，即1-n只有1条路径，直接求出路径长度和经过边数，简单计算得到答案

1号测试点中还有-1的情况

3,4号测试点n<=10，各种暴力通过

5,6号测试点-100<=t<=100

枚举答案，然后判断图中最短路是否存在，即1-n的路径上是否有负环存在。可以先用floyd传递闭包或者dfs将和1，n不连通的结点从图中去掉，然后用spfa算法来判负环。

复杂度上界为T*t*n^2*m

对于剩下的测试点，上述算法无法承受，考虑对其进行优化

枚举答案可以改成二分，负环可以用深搜版的spfa判（n*m），最终复杂度上界为T*logt*n*m