小雨坐地铁_牛客博客

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format:%lld

题目描述

小雨所在的城市一共有 m 条地铁线，分别标号为 1 号线，2 号线，……，m 号线。整个城市一共有 n 个车站，编号为 1∼n 。其中坐 i 号线需要花费 ai的价格，每坐一站就需要多花费 bi的价格。i 号线有 ci个车站，而且这 ci个车站都已知，如果某一站有多条地铁线经过，则可以在这一站换乘到另一条地铁线，并且能多次换乘。现在小雨想从第 ss 个车站坐地铁到第 t
个车站，地铁等待时间忽略不计，求最少花费的价格，若不能到达输出 -1 。（地铁是双向的，所以 s 可能大于 t）

输入描述:

第一行输入四个正整数 n,m,s,t分别表示车站个数，地铁线数，起点站和终点站。第二行到第 m + 1行，每行前三个数为
ai，bi,ci，分别表示坐 i 号线的价格，i 号线每坐一站多花的价格，i 号线车站个数。接下来 ci个数，表示 i
号线的每一个车站的编号，单调递增。

输出描述:
共一行，一个数表示最小花费，若不能到达输出 -1 。
示例1
输入

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

输出

说明
坐 1 号线：花费 2；
1→3：花费 2；

换乘 2 号线：花费 2；
3→4：花费 1；

所以最小总花费为 7 。

题解：
我也是毫无头绪，不知道该怎么下手做，看完别人的题解，来讲讲自己的理解
我们要用到分层图
建立m+1层图，前m层自然就是每一条的地铁线，但地铁线是有可能交叉的，也就是拥有共同车站，所以在第m+1层给每个车站建立一个虚点，用于和前m层对应的车站相连，注意是建双向边，因为地铁可来回，从虚点到地铁线上需要花费，花费坐这条线的价格，从地铁线上到虚点花费为0
具体可以看看图：

例题中求1—>4 ，
从虚点1出发，到第一条线1，花费为2，
从1再到3 花费为2
从第一条线3再到虚点3 花费为0
虚点3到第二条线3 花费为2
从第二条线3到4 花费为1
总花费为7

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e8+2;
int n,m,s,t,head[maxn],dis[maxn],ant,x;;
priority_queue<pair<int,int> ,vector<pair<int,int> >,greater<pair<int,int> > >q;
struct Node{
   
int to,next,w;
}edge[maxn<<1];

void add(int u,int v,int w)
{
   
	edge[ant].next = head[u];
    edge[++ant].to = v;
	edge[ant].w = w;
	
	head[u] = ant;
}
void dijkstra(int s)
{
   
	int u,d,v;
    dis[s] = 0;
  
    q.push(pair<int,int> (0,s));
    while(!q.empty())
    {
   
        u = q.top().second;
		d = q.top().first;
        q.pop();
        if(d > dis[u]) continue;
        for(int i=head[u];i;i=edge[i].next)
        {
   
             v = edge[i].to;
            if(dis[v] > dis[u]+edge[i].w)
            {
   
                dis[v] = dis[u]+edge[i].w;
                q.push(pair<int,int> (dis[v],v));
            }
        }
    }
}
int main()
{
    
	int a,b,c;
    cin>>n>>m>>s>>t;

	for(int i=1;i<=n*(m+1);++i) dis[i] = maxn;
    
	for(int i=1;i<=m;++i)
    {
   
       
        cin>>a>>b>>c;
        int pre = -1;
        while(c--)
        {
   
            cin>>x;
            if(pre != -1)
            {
   
                add(i*n+x,i*n+pre,b);
                add(i*n+pre,i*n+x,b);
            }
            
            add(x,i*n+x,a);//虚边到火车站费用是做这个火车的费用 
            
			add(i*n+x,x,0);//火车站到虚边费用为0 
			
			pre = x;//存上一个车站 
        }
    }

    dijkstra(s);
    if(dis[t] == maxn) cout<<"-1";
    else cout<<dis[t];
    return 0;
}