牛客 NC26257 小雨坐地铁
题目描述
小雨所在的城市一共有 mmm 条地铁线，分别标号为 1 号线，2 号线，……，m 号线。整个城市一共有 nnn 个车站，编号为 1∼n1 \sim n1∼n 。其中坐 i 号线需要花费 aia_iai 的价格，每坐一站就需要多花费 bib_ibi 的价格。i 号线有 cic_ici 个车站，而且这 cic_ici 个车站都已知，如果某一站有多条地铁线经过，则可以在这一站换乘到另一条地铁线，并且能多次换乘。现在小雨想从第 sss 个车站坐地铁到第 ttt 个车站，地铁等待时间忽略不计，求最少花费的价格，若不能到达输出 -1 。（地铁是双向的，所以 sss 可能大于 ttt）
输入描述:
第一行输入四个正整数 n,m,s,tn,m,s,tn,m,s,t，分别表示车站个数，地铁线数，起点站和终点站。 第二行到第 m+1m + 1m+1 行，每行前三个数为 ai,bi,cia_i,b_i,c_iai,bi,ci，分别表示坐 i 号线的价格，i 号线每坐一站多花的价格，i 号线车站个数。接下来 cic_ici 个数，表示 i 号线的每一个车站的编号，单调递增。输出描述:
共一行，一个数表示最小花费，若不能到达输出 -1 。示例1
输入
复制
5 2 1 4 2 2 3 1 3 5 2 1 4 2 3 4 5输出
复制
7说明
坐 1 号线：花费 2； 1→31 \rightarrow 31→3：花费 2； 换乘 2 号线：花费 2； 3→43 \rightarrow 43→4：花费 1； 所以最小总花费为 7 。备注:
1≤n≤103,1≤m≤500,1≤s,t≤n1 \leq n \leq 10^3, 1 \leq m \leq 500,1 \leq s,t \leq n1≤n≤103,1≤m≤500,1≤s,t≤n 1≤ai,bi≤100,1≤ci≤n,∑i=1mci≤1051 \leq a_i,b_i \leq 100,1 \leq c_i \leq n,\sum\limits_{i = 1}^m c_i \leq 10^51≤ai,bi≤100,1≤ci≤n,i=1∑mci≤105
思路：分层图最短路问题，将每条地铁线路单独看做一层，每一层的车站均与第m+1层的车站连接一条长度为0的路线，并反向连接一条长度为该地铁线路起步价的路线，同一层地铁站点之间连接一条长度为增值的路线，最后求第m+1层的s到t的最短路径；
建图如下所示：
AC代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=1010,M=1000010;
int n,m,S,E;
int h[M],e[M],ne[M],w[M],idx;
int dist[M];
bool st[M];
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void spfa()
{
memset(dist,0x3f,sizeof dist);
queue<int>q;
dist[n*m+S]=0;
st[n*m+S]=1;
q.push(n*m+S);
while(q.size())
{
int t=q.front();
q.pop();
st[t]=0;
for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[t]+w[i])
{
dist[j]=dist[t]+w[i];
if(!st[j])
{
q.push(j);
st[j]=1;
}
}
}
}
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d%d%d%d",&n,&m,&S,&E);
for(int i=1;i<=m;i++)
{
int prace,fee,x,pre;
scanf("%d%d%d",&prace,&fee,&x);
for(int j=1;j<=x;j++)
{
int a;
scanf("%d",&a);
add((i-1)*n+a,n*m+a,0);
add(n*m+a,(i-1)*n+a,prace);
if(j>1)
{
add((i-1)*n+pre,(i-1)*n+a,fee);
add((i-1)*n+a,(i-1)*n+pre,fee);
}
pre=a;
}
}
spfa();
if(dist[n*m+E]==0x3f3f3f3f)
puts("-1");
else
printf("%d\n",dist[n*m+E]);
}