http://www.lydsy.com/JudgeOnline/problem.php?id=4239 我们的4.12模拟赛T3 我写了很久又调了很久的spfa最后被硬刚到80分再也上不去了。。。 思路是把每辆车看做点，如果一辆车能换乘另一辆车就连上一条边 代码就不贴了吧（反正也看不懂） 网上看题解发现一种非常神奇的做法 我们维护到达每个点的最迟出发时间d和乘上每辆车的最迟出发时间dist 然后这两个东西可以互相维护 把所有车按照出发时间排序，再维护一个堆，维护每辆车的到达时间 更新d[i]=max（到达i点的车最迟出发时间） dist[i]=min（该车出发时间，到达i车起点的最迟出发时间） 最后离线处理答案，排序以后乱搞就好了。。。 详见代码
#include<bits/stdc++.h> using namespace std; inline int read(){ int k=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();} return k*f; } struct ppap{int x,p,s,t;}a[400001]; inline bool cmp(ppap a,ppap b){return a.s<b.s;} int ans[400001],prr=0; struct ppap1{int x,v;}xw[400001],pr[400001]; bool operator <(ppap1 a,ppap1 b){return a.v<b.v;} bool operator >(ppap1 a,ppap1 b){return a.v>b.v;} int d[400001]={0},dist[400001],n,m; priority_queue<ppap1,vector<ppap1>,greater<ppap1> >q; int main() { n=read();m=read(); for(int i=1;i<=m;i++)a[i].x=read(),a[i].p=read(),a[i].s=read(),a[i].t=read(); sort(a+1,a+m+1,cmp); memset(d,-1,sizeof d); d[1]=1e9; for(int i=1;i<=m;i++){ while(!q.empty()){ ppap1 p=q.top(); if(p.v<=a[i].s){ q.pop(); d[a[p.x].p]=max(d[a[p.x].p],dist[p.x]); }else break; } dist[i]=min(a[i].s,d[a[i].x]); ppap1 p;p.x=i;p.v=a[i].t;q.push(p); if(a[i].p==n)pr[++prr].v=a[i].t,pr[prr].x=dist[i]; } int qq=read(); for(int i=1;i<=qq;i++)xw[i].x=i,xw[i].v=read(); sort(xw+1,xw+qq+1); int anss=-1,rp=0; sort(pr+1,pr+prr+1); for(int i=1;i<=qq;i++){ while(pr[rp+1].v<=xw[i].v&&rp<prr)rp++,anss=max(anss,pr[rp].x); ans[xw[i].x]=anss; } for(int i=1;i<=qq;i++)printf("%d\n",ans[i]); return 0; }