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

2018-10-07 11:34:48


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$ 次免费机会的情况是否出现过.

对于某条路径我们可以选择使用机会,也可以选择不使用机会.

讨论这两种情况即可

#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);
}