C 小雨坐地铁

题目地址:

https://ac.nowcoder.com/acm/contest/5338/C

基本思路：

这题我们分层建图再跑最短路，对于每条地铁线我们建一层图，依次的两个站之间连双向的权值为b的边，然后对于换乘，我们多建一层的虚点，每条线的每个站到虚点的边设为0，从虚点出去到每条线的每个站的边权值设为a，这样我们就建图完成了，然后再跑一边dijkstra计算答案就好了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
const int maxn = 2050;
struct Edge{
  int to,val,next;
}edge[maxn * maxn*2];
int cnt = 0,head[maxn*maxn];
void add_edge(int u,int v,int w){
  edge[++cnt].next = head[u];
  edge[cnt].to = v;
  edge[cnt].val = w;
  head[u] = cnt;
}
int n,m,dis[maxn*maxn];
bool vis[maxn*maxn];
void dijkstra(int k){
  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> q;
  mset(dis,0x3f3f3f3f);
  mset(vis,false);
  dis[k] = 0;
  q.push(make_pair(0,k));
  while (!q.empty()){
    int s = q.top().second;
    q.pop();
    if(vis[s]) continue;
    vis[s] = true;
    for(int i = head[s];i!=-1;i = edge[i].next){
      if(dis[edge[i].to] > dis[s]+edge[i].val){
        dis[edge[i].to] = dis[s]+edge[i].val;
        q.push(make_pair(dis[edge[i].to],edge[i].to));
      }
    }
  }
}
int s,t;
signed main() {
  IO;
  cnt = 0;
  mset(head,-1);
  cin >> n >> m >> s >> t;
  rep(i,1,m){
    int a,b,c;
    cin >> a >> b >> c;
    int last = -1;
    rep(j,1,c){
      int x;
      cin >> x;
      if(last != -1){
        //每条地铁线路依次连边;
        add_edge((i-1)*n+x,(i-1)*n+last,b); 
        add_edge((i-1)*n+last,(i-1)*n+x,b);
      }
      //往虚点连边,表示换乘的状态;
      add_edge((i-1)*n+x,n*m+x,0);
      add_edge(n*m+x,(i-1)*n+x,a);
      last = x;
    }
  }
  dijkstra(n*m + s);
  // rep(i,1,n*m+n) cout << dis[i] << " ";
  // cout << '\n';
  if(dis[n*m + t] == INF) cout << -1 << '\n';
  else cout << dis[n*m + t] << '\n';
  return 0;
}