分析：（官方题解）
首先考虑暴力,显然可以直接每次O(n^2)
的连边,最后跑一次分层图最短路就行了.
然后我们考虑优化一下这个连边的过程 ,因为都是区间上的操作,所以能够很明显的想到利用线段树来维护整个图,
连边时候找到对应区间,把线段树的节点之间连边.这样可以大大缩减边的规模,然后再跑分层图最短路就可以了.
但是这样建图,每一次加边都要在O(logn)个线段树节点上加边,虽然跑的非常快,但是复杂度仍然是不科学的.
为了解决边的规模的问题,开两棵线段树,连边时候可以新建一个中间节点,在对应区间的节点和中间节点之间连边
进一步缩减了边的规模,强行下降一个数量级
最后跑一下分层图最短路就行了
复杂度O(mlog^2n)
什么你会线段树但是不会分层图最短路?安利JLOI2011飞行路线.
因为边的数目还是相对比较多的,所以不能使用SPFA,而要使用Heap-Dijkstra来做最短路,
但是不排除某些厉害的选手有特殊的SPFA姿势可以做或者普通 SPFA写的比较优美就不小心跑过去了...
注：出题人的题解写的很详细了，然后JLOI2011飞行路线是BZOJ2763 直接去做就好了
然后我的建图刚开始不太完善，跑了600+ms，然后后来完善了一下，按线段树节点建图（这就是题解）
不过每个线段树的节点不需要和它的区域内所有的点连边，只需要按照线段树的结构，连它的左右儿子就行了
代码：
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=5e4+;
int d[][N*+],head[N*+],tot,n,m,k;
struct Edge{
int v,w,next;
};
vector<Edge>edge;
void add(int u,int v,int w){
edge.push_back(Edge{v,w,head[u]});
head[u]=edge.size()-;
}
struct Node{
int cur,v,dis;
bool operator<(const Node &rhs)const{
return dis>rhs.dis;
}
};
priority_queue<Node>q;
bool vis[][N*+];
int dij(){
memset(d,INF,sizeof(d));
memset(vis,,sizeof(vis));
d[][*N+]=;
q.push(Node{,*N+,});
while(!q.empty()){
int cur=q.top().cur,u=q.top().v;
q.pop();
if(vis[cur][u])continue;
vis[cur][u]=;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].v;
if(!vis[cur][v]&&d[cur][v]>d[cur][u]+edge[i].w){
d[cur][v]=d[cur][u]+edge[i].w;
q.push(Node{cur,v,d[cur][v]});
}
if(cur+>k)continue;
if(!vis[cur+][v]&&d[cur+][v]>d[cur][u]){
d[cur+][v]=d[cur][u];
q.push(Node{cur+,v,d[cur+][v]});
}
}
}
return d[k][*N+n]==INF?-:d[k][*N+n];
}
void build(int rt,int l,int r){
if(l==r){
add(N*+l,rt,);
add(rt+*N,N*+l,);
return;
}
int mid=(l+r)>>;
build(rt<<,l,mid);
build(rt<<|,mid+,r);
add(rt<<,rt,),add(rt<<|,rt,);
add(rt+*N,*N+rt*,),add(rt+*N,*N+rt*+,);
}
int now,w;
void treeadd1(int rt,int l,int r,int x,int y){
if(x<=l&&r<=y){
add(rt,now,w);
return;
}
int mid=(l+r)>>;
if(x<=mid)treeadd1(rt<<,l,mid,x,y);
if(y>mid)treeadd1(rt<<|,mid+,r,x,y);
}
void treeadd2(int rt,int l,int r,int x,int y){
if(x<=l&&r<=y){
add(now,rt+*N,);
return;
}
int mid=(l+r)>>;
if(x<=mid)treeadd2(rt<<,l,mid,x,y);
if(y>mid)treeadd2(rt<<|,mid+,r,x,y);
}
int main(){
scanf("%d%d%d%d",&n,&n,&m,&k);
memset(head,-,sizeof(head));
edge.clear();
build(,,n);
now=*N;
for(int i=;i<=m;++i){
int a,b,c,d;
scanf("%d%d%d%d%d",&a,&b,&c,&d,&w);
++now;
treeadd1(,,n,a,b);
treeadd2(,,n,c,d);
++now;
treeadd1(,,n,c,d);
treeadd2(,,n,a,b);
}
int ans=dij();
if(ans==-)printf("CreationAugust is a sb!\n");
else printf("%d\n",ans);
return ;
}