Songhn Blog

NC26257 小雨坐地铁 题解

一道分层图建模的图论题
 ACM

题意简述

一个有$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代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

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

相关文章：