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 |
3 |
3 3 |
-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 + ;
const int inf = << ; 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 = , rear = ;
vector<Edge>E[maxn];
stack<int>ans; void spfa()
{
for(int i = ; i <= n ; ++ i)
arrive[i] = inf;
arrive[sp] = st;
memset(use,,sizeof(use));memset(pre,-,sizeof(pre));
q[rear] = sp , TIME[rear] = st , pre[rear++] = - ;
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 = ; 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+));
}
for(int i = ; 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\n");
else
{
int cur = front;
while(pre[cur] != -)
{
ans.push(door[cur]);
cur = pre[cur];
}
printf("%d\n",ans.size());
int flag = ;
while(!ans.empty())
{
if (flag)
flag = ;
else
printf(" ");
printf("%d",ans.top());ans.pop();
}
printf("\n");
}
return ;
}