D 坐地铁

https://ac.nowcoder.com/acm/contest/5556/D

解法1：

数组用二维分别表示点(station)和线路(line)两种状态；跑最短路的过程中， 先将当前点经过的所有line入队， 在跑邻接点的时候， 看和当前点是否在同一线内， 在的话则更新。表示sp到i点的最短距离，最后到i的线是第j条线

#include<bits/stdc++.h>
using namespace std;

#define sc scanf
#define MEM(x, b) memset(x, b, sizeof(x))

typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 2e3 + 100;
const int INF = 0x3f3f3f3f;
inline ll fpow(ll a, ll b){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t) % MOD; b >>= 1; t = (t*t) % MOD; }return r; }

struct Edge
{
    int v, k;
};
struct node
{
    int id, k, w;
    bool operator < (const node &oth) const
    {
        return w > oth.w;
    }
}mid;
vector <Edge> e[MAXN << 1];
vector <int> liEdge[MAXN << 1];
int dis[MAXN][MAXN], n, m, sp, tp;
int in[MAXN], nex[MAXN];//dis[i][j]表示sp到i点的最短距离，最后到i的线是第j条线
bool vis[MAXN][MAXN];
void dijkstra() {
    priority_queue <node> q;
    MEM(dis, INF); MEM(vis, 0);
    for (auto it : liEdge[sp]) {  // 起点线路全部入队
        dis[sp][it] = in[it];
        q.push({ sp, it, dis[sp][it] });
    }
    while (!q.empty()) {
        mid = q.top(); q.pop();
        int now = mid.id, line = mid.k;
        if (vis[now][line]) continue;
        vis[now][line] = true;
        for (auto it : liEdge[now]) {
            if (vis[now][it]) continue;
            if (dis[now][it] > dis[now][line] + in[it]) { //下一个线路
                dis[now][it] = dis[now][line] + in[it];
                q.push({ now, it, dis[now][it] }); 
            }
        }
        for (int i = 0; i <e[now].size(); i++) {
            int vi = e[now][i].v, fi = e[now][i].k;  // 同一条线才更新
            if (fi != line) continue;
            if (dis[vi][fi] > dis[now][line] + nex[line]) {
                dis[vi][fi] = dis[now][line] + nex[line];
                q.push({ vi, fi, dis[vi][fi] });
            }
        }
    }
}

int main()
{
    cin >> n >> m >> sp >> tp;
    for (int i = 1; i <= m; i++) {
        int num, tmp; sc("%d %d %d", &in[i], &nex[i], &num); //in表示进线，next表示下一站的费用
        int last = 0;
        for (int j = 1; j <= num; j++) {
            sc("%d", &tmp);
            liEdge[tmp].push_back(i); // 该站台包含的线路
            if (last) {
                e[last].push_back({ tmp, i });  // 依次连线
                e[tmp].push_back({ last, i });
            }
            last = tmp;
        }
    }
    if (sp == tp) { cout << 0 << endl; return 0; }
    dijkstra();
    int ans = INF;
    for (int i = 1; i <= m; i++) ans=min(ans,dis[tp][i]);
    if (ans == INF) cout << -1 << endl;
    else cout << ans << endl;
    return 0;  
}

解法2：

这个解法代码更加简洁---dis只需要一维。手动添加一些虚点（每个点都有对应的虚点），在换线路时必须经过这些虚点，虚点到真实点的距离为"入场费"，真实点到虚点距离为0，这样直接跑最短路即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int maxn = 1e3 + 5;

int n, m, s, t;
int head[500 * maxn], cnt;
int to[maxn * 1000], nxt[maxn * 1000], val[maxn * 1000];

void addEdge(int a, int b, int c) {
    to[++ cnt] = b, val[cnt] = c;
    nxt[cnt] = head[a], head[a] = cnt;
}

bool vis[maxn * 500];
int dis[maxn * 500];
void dijkstra(){
    priority_queue<P> que;
    que.push(P(0, s));
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    while(!que.empty()) {
        P p = que.top(); que.pop();
        int u = p.second;
        if(u == t) {
            cout << -p.first << endl;
            return ;
        }
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            if(dis[v] > dis[u] + val[i]) {
                dis[v] = dis[u] + val[i];
                que.push(P(-dis[v], v));
            }
        }
    }
    cout << -1 << endl;
}

int main(){
    cin >> n >> m >> s >> t;
    for(int i = 1, a, b, c; i <= m; i ++) {
        cin >> a >> b >> c;
        for(int j = 1, u, v; j <= c; j ++) {
            cin >> v;
            if(j > 1){
                addEdge((i - 1) * n + u, (i - 1) * n + v, b);
                addEdge((i - 1) * n + v, (i - 1) * n + u, b);
            }
            addEdge((i - 1) * n + v, m * n + v, 0);
            addEdge( m * n + v,      (i - 1) * n + v, a);//每个点都有一个虚点，入站费用
            u = v;
        }
    }
    t = n * m + t;//转换成虚点
    s = n * m + s;
    dijkstra();
    return 0;
}