NC26257 小雨坐地铁 题解


题意简述

一个有$n$个点的图有$m$条地铁线,每条线路$i$乘坐需要花费$a_i$,每坐一站需要多花费$b_i$,每条线路有$c_i$个站点按顺序连过,每个线路都是双向边。现在从$s$到$t$中间可以多次换乘,问最少花费,如不可到达则输出-1

$1≤n≤10 ^3,1≤m≤500,1≤s,t≤n$
$1\leq a_i,b_i\leq 100,1\leq c_i\leq n,\sum_{i=1}^m{c_i}\leq 10^5$


样例

输入

5 2 1 4
2 2 3 1 3 5
2 1 4 2 3 4 5

输出

7

题解

好久没写题解了呜呜

这道题假如按照常规思路去做的很多细节其实蛮难处理的,但是假如采取分层图的思想去做就会清晰很多,所以就记录一下分层图的这种做法

首先我们需要对每个地铁都建一层图,每层图都有$n$个点,所以一共有$n\cdot m$个点,最后把原始的图也就是原本的$n$个节点作为第$m+1$层图,下面我们考虑一下怎么连边

每一层的地铁还是比较好想的,对于一条线路每两个站点都连边权为$b_i$的双向边,之后就是重点,对于当前层的每一个点,我们向第$m+1$层的对应的点连一条边权为$0$的单向边,然后反向连一条边权为$a$的单向边

这一步是在干什么呢?我们把第$m+1$层的图看成主体,这样在这层的每个点,我们就能获取到所有的乘车情况,因为地铁每个线路的对应点都与它相连,由于这是换乘,所以需要花费$a_i$,这就是从$m+1$层往其他层连需要$a_i$花费的原因

换乘之后我们会在这层铁路正常行驶,假如有再次换乘的话,其实就是对应回到第$m+1$层之后选择所有可以换乘的线路,所以题目所有的要求都被我们满足了,在这个分层图上我们从第$m+1$层的$s$节点跑一边最短路,第$m+1$层的$t$节点的最短路就是答案

AC代码

template<class T>inline void rd(T &x) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
}
const int inf=0x3f3f3f3f;
const int maxn=1000010;
int n,m,s,t;
int head[maxn],num;
int st,ed;
int dis[maxn],vis[maxn];
struct node{
    int v,w,nex;
}e[maxn];
void add(int u,int v,int w)
{
    e[++num].nex=head[u];
    e[num].v=v;e[num].w=w;
    head[u]=num;
}
void dij()
{
    mst(dis,0x3f);
    priority_queue<PII,vector<PII>,greater<PII> > q;
    while(!q.empty()) q.pop();
    q.push(make_pair(0,st));
    dis[st]=0;
    while(!q.empty())
    {
        int u=q.top().second;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].nex)
        {
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w)
            {
                dis[v]=dis[u]+e[i].w;
                q.push(make_pair(dis[v],v));
            }
        }
    }
}
int main()
{
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;rd(a),rd(b),rd(c);
        int pre;rd(pre);
        add(n*m+pre,(i-1)*n+pre,a);
        add((i-1)*n+pre,n*m+pre,0);
        for(int j=2;j<=c;j++)
        {
            int v;rd(v);
            add(n*m+v,(i-1)*n+v,a);
            add((i-1)*n+v,m*n+v,0);
            add((i-1)*n+pre,(i-1)*n+v,b);
            add((i-1)*n+v,(i-1)*n+pre,b);
            pre=v;
        }
    }
    st=n*m+s,ed=n*m+t;
    dij();
    if(dis[ed]!=inf) cout<<dis[ed]<<endl;
    else puts("-1");
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
  目录