题解 P4568 【[JLOI2011]飞行路线】

顾z

2018-10-07 11:34:48

Solution

>### Description >Alice和Bob现在要乘飞机旅行,他们选择了一家相对便宜的航空公司。该航空公司一共在nn个城市设有业务,设这些城市分别标记为$0$到$n−1$,一共有$m$种航线,每种航线连接两个城市,并且航线有一定的价格。 >Alice和Bob现在要从一个城市沿着航线到达另一个城市,途中可以进行转机。航空公司对他们这次旅行也推出优惠,他们可以免费在最多$k$种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少? >### Input >数据的第一行有三个整数,$n,m,k$,分别表示城市数,航线数和免费乘坐次数。 >第二行有两个整数,$s,t$,分别表示他们出行的起点城市编号和终点城市编号。 >接下来有$m$行,每行三个整数,$a,b,c$,表示存在一种航线,能从城市$a$到达城市$b$,或从城市$b$到达城市$a$,价格为$c$。 >### Output >只有一行,包含一个整数,为最少花费 ### 分析 ​ 明显,此题为最短路问题,但是考虑到可以免费搭乘(即直接通过一条边无需费用.) 这种问题有一个官方的名字 **分层图最短路问题** > 分层图最短路是指在可以进行分层图的图上解决最短路问题. 是不是听起来就很nb? ~~具体分层图是啥,我也不知道~~ > 一般模型: > > ​  在图上,有$k$次机会可以直接通过一条边,问起点与终点之间的最短路径. 很明显,这道题是一个裸的分层图最短路问题 (貌似这类问题都挺裸的 emm #### 解法 我们设 > $dis[i][j]$代表到达$i$用了$j$次免费机会的最小花费. > > $vis[i][j]$代表到达$i$用了$j$次免费机会的情况是否出现过. 对于某条路径我们可以选择使用机会,也可以选择不使用机会. 讨论这两种情况即可 ```c++ #include<cstdio> #include<queue> #include<cstring> #define R register #define N 20008 using namespace std; inline void in(int &x) { int f=1;x=0;char s=getchar(); while(s>'9' or s<'0'){if(s=='-')f=-1;s=getchar();} while(s>='0' and s<='9'){x=x*10+s-'0';s=getchar();} x*=f; } int head[N],tot,n,m,s,t,k; int dis[N][15],ans=2147483647; bool vis[N][15]; struct cod{int u,v,w;}edge[N*6+8]; inline void add(int x,int y,int z) { edge[++tot].u=head[x]; edge[tot].v=y; edge[tot].w=z; head[x]=tot; } struct coc{ int u,d,used; bool operator <(const coc&a) const { return d>a.d; } }; inline void dijkstra() { memset(dis,127,sizeof dis); dis[s][0]=0; priority_queue<coc>q; q.push((coc){s,0,0}); while(!q.empty()) { int u=q.top().u,now=q.top().used; q.pop(); if(vis[u][now])continue; vis[u][now]=true; for(R int i=head[u];i;i=edge[i].u) { if(now<k and !vis[edge[i].v][now+1] and dis[edge[i].v][now+1]>dis[u][now])//当前路径,使用一次免费机会.注意判断 now<k { dis[edge[i].v][now+1]=dis[u][now]; q.push((coc){edge[i].v,dis[edge[i].v][now+1],now+1}); } if(!vis[edge[i].v][now] and dis[edge[i].v][now]>dis[u][now]+edge[i].w)//当前路径,不使用免费机会 { dis[edge[i].v][now]=dis[u][now]+edge[i].w; q.push((coc){edge[i].v,dis[edge[i].v][now],now}); } } } } int main() { in(n),in(m),in(k); in(s),in(t); s++;t++;//这里个人习惯不同.我选择记录编号为1~n for(R int i=1,x,y,z;i<=m;i++) { in(x),in(y),in(z); x++;y++; add(x,y,z); add(y,x,z); } dijkstra();//直接跑dijkstra for(R int i=0;i<=k;i++) ans=min(ans,dis[t][i]);//到达t我们需要对使用免费机会的情况枚举.取min printf("%d",ans); } ```