没有题面。
首先最短路判断一下有没有输出 -1 的情况。
然后把握答案可以二分求解的特点，那就很容易解决了。
令边中最大的年代为 maxx
那么就在[1,maxx]中进行二分求解，枚举年代mid，跑一遍最短路，不走年代<=mid的边，然后判断dis[n]是否>=T，如果>=说明mid可能偏大，否则mid可能偏小。
怎么优化？
把所有边的年代存下来，sort一次，然后在这些数据里面二分（mid只能是出现过的年代）。
优化你的最短路算法，例如SPFA的LLL优化与SLF优化
二分暴力求解即可。
1 #include2 #include 3 #include 4 using namespace std; 5 template inline void read(T &_a){ 6 int _ch=getchar();_a=0; 7 while(_ch<'0' || _ch>'9')_ch=getchar(); 8 while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();} 9 }10 11 const int maxn=20001,maxm=100001;12 int n,m,T,egcnt,head[maxn],q[maxn],dis2[maxn],dis[maxn],tail,h,maxx;13 bool ins[maxn],vis[maxn];14 struct edge{15 int next,to,dis,year;16 }w[maxm<<1];17 18 inline void addedge(int from,int to,int dis,int year)19 {20 w[++egcnt].dis=dis;21 w[egcnt].to=to;22 w[egcnt].year=year;23 w[egcnt].next=head[from];24 maxx=max(maxx,year);25 head[from]=egcnt;26 }27 28 inline void spfa(int y){29 memset(dis,0x7f,sizeof(dis));30 dis[1]=0; q[1]=1; h=0; tail=1;31 while(h!=tail)32 {33 h=h%20000+1;34 int now=q[h];35 ins[now]=false;36 for (register int i=head[now];i;i=w[i].next)37 if(w[i].year>y){38 if(dis[w[i].to]>dis[now]+w[i].dis)39 {40 dis[w[i].to]=dis[now]+w[i].dis;41 if(!ins[w[i].to])42 {43 ins[w[i].to]=true;44 tail=tail%20000+1;45 q[tail]=w[i].to;46 }47 }48 }49 }50 }51 52 int main()53 {54 read(n); read(m); read(T);55 for (register int i=1,s,t,l,y;i<=m;++i) read(s),read(t),read(l),read(y),addedge(s,t,l,y);56 spfa(0);57 if(dis[n]>=T) { printf("-1 %d",dis[n]); return 0; }58 int l=1,r=maxx;59 while(l<=r)60 {61 memset(vis,0,sizeof(vis));62 int mid=l+r>>1;63 spfa(mid);64 if(dis[n]