C - 秋实大哥与时空漫游
Time Limit: 4500/1500MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
秋实大哥通过全国的连锁快餐店发家致富，赚了大钱，接下来他打算通过这些钱实现他的另一个梦想————遨游太空，漫游星际。
秋实大哥满怀期待的出发了。
.......啦啦啦啦啦啦啦啦啦......
最后，秋实大哥花完了钱，觉得是时候回地球继续赚钱和过节了。
但是却被告知回地球的专机只有一架————在Tp星球且在Tt时刻起飞（因此必须要在Tt时刻之前到达该Tp星球），而秋实大哥现在所处的时空是Sp星球上的St时刻。为了能赶上那班回地球的专机，秋实大哥可以使用一系列的时空传送门。
（时空传送门是发达星球的日常交通产物，而像地球这样的发展中星球只有最原始的宇宙飞船。）
每个传送门有4个属性，起点星球a，终点星球b，起点时刻c，终点时刻d。如果秋实大哥想使用某时空传送门，那么他就必须在c时刻之前到达星球a，然后等到c时刻他就可以通过该传送门到达d时刻的星球b。
在任意时刻，如果在同一星球上有两个秋实大哥，就会引发“祖父悖论”！
这就犯了时空漫游的大忌，时空就会扭曲，宇宙就会产生巨大的黑洞甚至引发降维，世界就会毁灭！
得知稍有不当就会毁灭世界，秋实大哥现在很慌，不知道到底怎么走才能赶上回地球的末班车。
但是迫不及待想见到秋实大哥的你马上给出了正确答案。
Input
第一行一个整数N,M，分别表示星球的个数和传送门的个数
接下来M行，表示每个传送门的四个属性ai,bi,ci,di。
最后一行四个整数Sp,Tp,St,Tt分别表示秋实大哥所处的初始时刻和星球，以及末班车的地点和时间。
1≤Sp,Tp,ai,bi≤N
0≤St,Tt,ci,di≤107
N≤105,M≤5×105
Output
如果秋实大哥无论如何都不能赶上，输出-1。
否则：
第一行一个整数k，表示秋实大哥所要经历的传送门个数。
第二行k个整数，按顺序输出秋实大哥使用传送门编号（从1开始编号）。
任意的合法解都是支持的。
Sample input and output
| Sample Input | Sample Output |
|---|---|
3 3 1 2 4 2 2 1 2 1 1 1 1 0 1 1 3 0 |
3 1 2 3 |
3 3 1 2 4 2 2 1 2 1 1 1 1 0 1 2 0 1 |
-1 |
解题思路:
抓住题目的重要条件 ：通过传送门到达的另外一个点的时间是固定的！！！
1.令 arrive[i] 表示能够到达 i 星球的最早时刻.<其实理解之后这个arrive[i]完全可以换成第多少个传送门>
-> 对所有点的边按照出发时间从 小到大 排序.（这步非常重要）
2.用 use[i] 表示对于点 i 来讲，已经跑完了 use[i] + 1 -> E[i].size() - 1 这些边，0 - > use[i] 这些边还没有跑
3.跑 spfa , 对于某个点来讲，如果新过去的时间大于等于 E[ use[target] ].begtime , 更新即可
但是，这样做为什么是对的呢？
如果过去的时间没有到达下一个传送门所要求的时限，那么我们根据题目的重要条件，到达其他星球的时间根本不会变化，所以这是没有必要的！
例子: 某星球的传送门开启时刻（已排序）
10 50 100 200 300
假定现在arrive[this_plant] = 175（即目前到达这个星球的最早时间是 175 )
那么假如现在，我可以从某个另外一个星球到达这个星球的时间是 101 ，那么有必要入队么？显然没有必要，入了也没用，你能搞的传送门还是后面几个，同时根据题目
的重要条件（※），对其他点的arrive[]不会产生影响，所以不入队
那么如果这个时间是 75 呢，显然必须入队了， 因为这个时候又可以走一个新的传送门 100 了，所以说这个时候是需要入队的!
根据这个例子，肯定也就知道给点的边出发时间排序的作用了.
但是这题的关键是找路径，一种办法是记录边的前驱边（但是我WA了很多次，虽然逻辑上认为是对的，但。。。。事实太残酷）
后来我思考后，发现边的前驱其实是可以，但是我们需要加上一个虚拟边，就是终点的传送门边，这样才能正确，具体。。就没有实现了
后来AC使用的办法是队列位置回溯，因为题目并不要求最短路径，那么一旦到达了终点且时间≤起飞时间，就立即停止spfa，并通过回溯队列位置找答案.
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <vector> #include <stack> using namespace std; const int maxn = 6e5; const int maxsize = 1e6 + 500; const int inf = 1 << 28; typedef struct Edge { int v,c,d,id; Edge(const int &v,const int &c,const int &d,const int &id) { this->v = v , this->c = c , this->d = d , this->id = id; } friend bool operator < (const Edge & x,const Edge& y) { return x.c > y.c; } }; int q[maxsize]; int pre[maxsize]; int door[maxsize]; int TIME[maxsize]; int use[maxn]; int n,m,sp,tp,st,tt; int arrive[maxn]; int front = 0 , rear = 0; vector<Edge>E[maxn]; stack<int>ans; void spfa() { for(int i = 1 ; i <= n ; ++ i) arrive[i] = inf; arrive[sp] = st; memset(use,0,sizeof(use));memset(pre,-1,sizeof(pre)); q[rear] = sp , TIME[rear] = st , pre[rear++] = -1 ; while(front < rear) { int x = q[front]; int cmp = TIME[front]; if (x == tp && cmp <= tt) break; //到达终点，立即退出 for( ; use[x] < E[x].size() && E[x][use[x]].c >= cmp ; ++ use[x] ) { int v= E[x][use[x]].v; if (arrive[v] > E[x][use[x]].d) { arrive[v] = E[x][use[x]].d; door[rear] = E[x][use[x]].id; pre[rear] = front; TIME[rear] = E[x][use[x]].d; q[rear++] = v; } } front++; } } int main(int argc,char *argv[]) { scanf("%d%d",&n,&m); for(int i = 0 ; i < m ; ++ i) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); E[a].push_back(Edge(b,c,d,i+1)); } for(int i = 1 ; i <= n ; ++ i) sort(E[i].begin(),E[i].end()); scanf("%d%d%d%d",&sp,&tp,&st,&tt); spfa(); if (arrive[tp] > tt) printf("-1 "); else { int cur = front; while(pre[cur] != -1) { ans.push(door[cur]); cur = pre[cur]; } printf("%d ",ans.size()); int flag = 1; while(!ans.empty()) { if (flag) flag = 0; else printf(" "); printf("%d",ans.top());ans.pop(); } printf(" "); } return 0; }