首页 > 代码库 > 2014.10.28模拟赛【时间与空间之旅】
2014.10.28模拟赛【时间与空间之旅】
Porble 1时间与空间之旅(tstrip.*)
题目描述
公元22××年，宇宙中最普遍的交通工具是spaceship。spaceship的出现使得星系之间的联系变得更为紧密，所以spaceship船长也成了最热门的职业之一。当然，要成为一名出色的船长，必须通过严格的考核，例如下面是最简单的问题中的一个。
用1~n的整数给n个星系标号，目前你在标号为1的星系，你需要送快递到标号为n的星系，星系之间由于存在陨石带，并不是都可以直连的。同时，由于超时空隧道的存在，在某些星系间飞行会出现时间静止甚至倒流，飞行时间为0或为负数。另外,由星系i到星系j的时间和由星系j到星系i的时间不一定是相同的。
在寄出日期之前收到快递被认为是不允许的，所以每部spaceship上都有一个速度调节装置，可以调节飞行的时间。简单来说其功能就是让所有两个星系间的飞行时间(如果可以直达)都增加或减少相同的整数值，你的任务就是调整速度调节器，找出一条用最短时间完成任务的路径，并且保证这个最短时间的值大于或等于0。
输入格式
输入文件包含多组数据，第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最多只会有一条飞行线路。
输出格式
输出文件共T行，每组数据输出一行；
如果可以通过调节速度调节器完成任务，则输出一个非负整数，表示由星系1到星系N的最短时间。
如果不能由星系1到达星系N，则输出-1。
输入样例
1
4 5
1 2 1
1 3 1
2 3 -3
3 1 1
3 4 1
输出样例
2
样例说明
输入样例如图所示，其中节点标号表示相应星系，节点间数字表示所需时间。
如果设置速度控制器的值为0，则有如下路径:1→2→3→1→2→……→3→4，使得投递的时间为负无穷大，显然是不符合要求的，所以应该把速度控制器的值设为1,相当于每个时间值加1,得到的最短路径为1→2→3→4,所需时间为2+(-2)+2=2。
我说把广东省选题拿来考NOIP真的好吗
题意是要把所有的边加上或者减去一个值，使得最短路没有负环，输出最小非负解
要二分加上去的数字。这个没问题
然后要判断在最短路的路径上没有负环。不仅是判断负环的问题，还要求在最短路的路径上
因此在spfa判负环的基础上做这样的处理：
首先floyd预处理出各个点之间的连通性。我们只更新可以到达目标点的状态
即当当前这个点可以到达n点的时候才更新
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<deque> 9 #include<set> 10 #include<map> 11 #include<ctime> 12 #define LL long long 13 #define inf 598460606 14 #define pa pair<int,int> 15 #define pi 3.1415926535897932384626433832795028841971 16 #define mod 100007 17 using namespace std; 18 struct edge{ 19 int to,next,v; 20 }e[1000010]; 21 int head[100010]; 22 int rep[100010]; 23 int dist[100010]; 24 bool mrk[100010]; 25 int go[110][110]; 26 int q[mod]; 27 int T,n,m,l,r,cnt,ans; 28 inline void ins(int u,int v,int w) 29 { 30 e[++cnt].to=v; 31 e[cnt].v=w; 32 e[cnt].next=head[u]; 33 head[u]=cnt; 34 } 35 inline int jud(int lim) 36 { 37 for (int i=1;i<=n;i++)mrk[i]=0; 38 for (int i=1;i<=n;i++)dist[i]=inf; 39 for (int i=1;i<=n;i++)rep[i]=0; 40 memset(q,0,sizeof(q)); 41 q[1]=1;mrk[1]=1;dist[1]=0;rep[1]=1; 42 int t=0,w=1; 43 while (t<w) 44 { 45 int now=q[++t]; 46 mrk[now]=0; 47 for (int i=head[now];i;i=e[i].next) 48 { 49 if (dist[e[i].to]>dist[now]+e[i].v+lim&&go[e[i].to][n]) 50 { 51 dist[e[i].to]=dist[now]+e[i].v+lim; 52 53 if (!mrk[e[i].to]&&rep[e[i].to]<=n) 54 { 55 mrk[e[i].to]=1; 56 rep[e[i].to]++; 57 if (rep[e[i].to]>n)return -1; 58 q[++w]=e[i].to; 59 } 60 } 61 } 62 } 63 return dist[n]; 64 } 65 inline void work() 66 { 67 memset(e,0,sizeof(e)); 68 memset(head,0,sizeof(head)); 69 memset(go,0,sizeof(go)); 70 cnt=0; 71 scanf("%d%d",&n,&m); 72 int mn=inf; 73 int mx=-inf; 74 for (int i=1;i<=m;i++) 75 { 76 int x,y,z; 77 scanf("%d%d%d",&x,&y,&z); 78 ins(x,y,z); 79 mn=min(mn,z); 80 mx=max(mx,z); 81 go[x][y]=1; 82 } 83 for(int i=1;i<=n;i++)go[i][i]=1; 84 for(int k=1;k<=n;k++) 85 for(int i=1;i<=n;i++) 86 for(int j=1;j<=n;j++) 87 go[i][j]=go[i][j]|(go[i][k]&go[k][j]); 88 if (!go[1][n]){printf("-1\n");return;} 89 l=-mx;r=-mn; 90 ans=-1; 91 while (l<=r) 92 { 93 int mid=(l+r)>>1,now=jud(mid); 94 if (now>=0&&now!=inf){ans=now;r=mid-1;} 95 else l=mid+1; 96 } 97 printf("%d\n",ans); 98 } 99 int main()100 {101 freopen("tstrip.in","r",stdin);102 freopen("tstrip.out","w",stdout);103 scanf("%d",&T);104 while (T--)work();105 }
2014.10.28模拟赛【时间与空间之旅】