题目
题目描述
小雨所在的城市一共有 \(m\) 条地铁线，分别标号为 1 号线，2 号线，……，m 号线。整个城市一共有 \(n\) 个车站，编号为 \(1 \sim n\) 。其中坐 i 号线需要花费 \(a_i\) 的价格，每坐一站就需要多花费 \(b_i\) 的价格。i 号线有 \(c_i\) 个车站，而且这 \(c_i\) 个车站都已知，如果某一站有多条地铁线经过，则可以在这一站换乘到另一条地铁线，并且能多次换乘。现在小雨想从第 s 个车站坐地铁到第 t 个车站，地铁等待时间忽略不计，求最少花费的价格，若不能到达输出 -1 。（地铁是双向的，所以 s 可能大于 t）
输入描述
第一行输入四个正整数 \(n,m,s,t\)，分别表示车站个数，地铁线数，起点站和终点站。
第二行到第 \(m + 1\) 行，每行前三个数为 \(a_i,b_i,c_i\)，分别表示坐 i 号线的价格，i 号线每坐一站多花的价格，i 号线车站个数。接下来 \(c_i\) 个数，表示 i 号线的每一个车站的编号，单调递增。
输出描述
共一行，一个数表示最小花费，若不能到达输出 -1 。
示例1
输入
5 2 1 4
2 2 3 1 3 5
2 1 4 2 3 4 5
输出
7
说明
坐 1 号线：花费 2；
\(1 \rightarrow 3\) ：花费 2；
换乘 2 号线：花费 2；
\(3 \rightarrow 4\) ：花费 1；
所以最小总花费为 7 。
备注
\(1 \leq n \leq 10^3, 1 \leq m \leq 500,1 \leq s,t \leq n\)
\(1 \leq a_i,b_i \leq 100,1 \leq c_i \leq n,\sum\limits_{i = 1}^m c_i \leq 10^5\)
题解
知识点：图论建模，最短路。
利用分层图建模，每条地铁单独建立 \(n\) 个点。再额外建立 \(n\) 个点作为换乘的点，连接每条地铁每站。
最后跑最短路即可。
时间复杂度 \(O((nm+\sum c_i)\log\sum c_i)\)
空间复杂度 \(O(nm+\sum c_i)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3 * 501 + 7, M = 4 * 1e5 + 7;
template<class T>
struct Graph {
struct edge {
int v, nxt;
T w;
};
int idx;
vector<int> h;
vector<edge> e;
Graph(int n, int m) :idx(0), h(n + 1), e(m + 1) {}
void clear(int n, int m) {//全局使用时清零，确定范围防止超时
idx = 0;
h.assign(n + 1, 0);
e.assign(m + 1, { 0,0,0 });
}
void add(int u, int v, T w) {
e[++idx] = edge{ v,h[u],w };
h[u] = idx;
}
};
Graph<int> g(N, M);
bool vis[N];
int dis[N];
struct node {
int v, w;
friend bool operator<(node a, node b) {
return a.w > b.w;
}
};
priority_queue<node> pq;
void dijkstra(int st) {
memset(dis, 0x3f, sizeof(dis));
dis[st] = 0;
pq.push({ st,0 });
while (!pq.empty()) {
int u = pq.top().v;
pq.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = g.h[u];i;i = g.e[i].nxt) {
int v = g.e[i].v, w = g.e[i].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
pq.push({ v,dis[v] });
}
}
}
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m, s, t;
cin >> n >> m >> s >> t;
for (int i = 1;i <= m;i++) {
int a, b, c;
cin >> a >> b >> c;
int pre = 0;
while (c--) {
int x;
cin >> x;
if (pre) {
g.add(pre + i * n, x + i * n, b);
g.add(x + i * n, pre + i * n, b);
}
//每层用以站点在不同线路连接，第一层当作站点，用以换乘
g.add(x, x + i * n, a);
g.add(x + i * n, x, 0);
pre = x;
}
}
dijkstra(s);
cout << (dis[t] > 1e9 ? -1 : dis[t]) << '\n';
return 0;
}