http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=688&pid=1005
题意:
略
题解:
邀请赛前复习一下板子..
线段树优化建图+分层图最短路
在dij里面写松弛会不少一些,如果真的建了11层图,貌似会T
(都9102年了,hdu还是不支持c11)
#include <bits/stdc++.h>
#define endl '
'
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(ii,a,b) for(register int ii=a;ii<=b;++ii)
#define forn(ii,now) for(register int ii=head[now];ii;ii=e[ii].next)
using namespace std;
const int maxn=1e6+10,maxm=2e6+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
int casn,n,m,k,q,s,num[maxn];
class graph{public:
struct node{int to,next;ll cost;}e[maxn];
int head[maxn],nume;
inline void add(int a,int b,ll c){
e[++nume]={b,head[a],c};
head[a]=nume;
}
void init(int n){memset(head,0,(n+1)<<2);nume=1;}
struct road{
int now,use;ll dis;
road(int a,ll b,int c){now=a,dis=b;use=c;}
bool operator<(const road &rhs)const{return dis>rhs.dis;}
};
ll dis[maxn][12];priority_queue<road>q;
void getdis(int st,int n=maxn-10){
memset(dis,0x3f,(sizeof dis[0])*(n+1));q.emplace(st,0,0);
memset(dis[1],0,sizeof dis[1]);
while(!q.empty()){
road t=q.top();q.pop();
forn(i,t.now){
node ee=e[i];
ll cost=t.dis+ee.cost;
if(cost<dis[ee.to][t.use]){
dis[ee.to][t.use]=cost;
q.emplace(ee.to,cost,t.use);
}
if(t.use<k&&t.dis<dis[ee.to][t.use+1]){
dis[ee.to][t.use+1]=t.dis;
q.emplace(ee.to,t.dis,t.use+1);
}
}
}
}
}g;
int cnt;
class segtree{public:
#define nd node[now]
#define ndl node[now<<1]
#define ndr node[now<<1|1]
int flag;//1==intree,0==outtree
struct segnode {
int l,r,id;
inline int mid(){return (r+l)>>1;}
inline int len(){return r-l+1;}
};
segnode node[maxn<<2|3];
vector<int> v;
void init(int n,int flag){
this->flag=flag;
maketree(1,n);
}
void pushup(int now){
if(!flag){
g.add(nd.id,ndl.id,0);
g.add(nd.id,ndr.id,0);
}else {
g.add(ndl.id,nd.id,0);
g.add(ndr.id,nd.id,0);
}
}
void maketree(int s,int t,int now=1){
nd={s,t,++cnt};
if(s==t){
if(flag) g.add(s,nd.id,0);
else g.add(nd.id,s,0);
return ;
}
maketree(s,nd.mid(),now<<1);
maketree(nd.mid()+1,t,now<<1|1);
pushup(now);
}
vector<int> query(int s,int t){v.clear();find(s,t);return v;}
void find(int s,int t,int now=1){
if(s<=nd.l&&t>=nd.r) {
v.emplace_back(nd.id);
return ;
}
if(s<=ndl.r) find(s,t,now<<1);
if(t>ndl.r) find(s,t,now<<1|1);
}
}intree,outree;
int main() {
IO;cin>>casn>>n>>m>>k;cnt=n;
g.init(n*20);
intree.init(n,1);
outree.init(n,0);
rep(i,1,m){
int a,b,c,d;ll w;cin>>a>>b>>c>>d>>w;
vector<int> in=intree.query(a,b),out=outree.query(c,d);
++cnt;
int sz=in.size();
for(int i=0,p=in[0];i<sz;++i,p=in[i]) g.add(p,cnt,w);
sz=out.size();
for(int i=0,p=out[0];i<sz;++i,p=out[i]) g.add(cnt,p,0);
in=intree.query(c,d),out=outree.query(a,b);
++cnt;
sz=in.size();
for(int i=0,p=in[0];i<sz;++i,p=in[i]) g.add(p,cnt,w);
sz=out.size();
for(int i=0,p=out[0];i<sz;++i,p=out[i]) g.add(cnt,p,0);
}
g.getdis(1,cnt);
ll ans=INF;
rep(i,0,k) ans=min(ans,g.dis[n][i]);
if(ans<INF) cout<<ans<<endl;
else cout<<"CreationAugust is a sb!"<<endl;
}