牛客小白月赛16 小雨坐地铁 分层图 ，最短路

小雨坐地铁

官方题解：
考虑分层图最短路。
很容易想到建 m 层图，如果多条地铁线都经过同一个点，则在这些点之间暴力两两连边，这样连边是 O(n) 的，可能会超时。
我们可以多建一层虚点，所有点到它对应的虚点不需要代价，从虚点到它对应的点需要对应的代价，这样就可以优化到 O(nm) 建图。最后跑一边最短路就好了。

建m层图，

0 ~ m-1 层表示每条线路。

第m层是虚点，m层的第 i 个点，可以到达任一层的 i 点，需要支付的对应的钱，从任一 i 点到m层 i 点不需要费用。

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ll long long
#define INF 0x3f3f3f3f
const int N = 1e6+100;

int n, m, s, t;

struct Edge{
	int to, next, w;
	Edge(){}
	Edge(int to, int next, int w):to(to),next(next),w(w){}
}e[2*N];
int head[N], tot = 0;

void addEdge(int u,int v,int w){
	e[tot] = Edge(v,head[u],w);
	head[u]=tot++;
}
int vis[N];
ll dis[N];
void Dijsktra(){
	memset(dis,INF,sizeof dis);
	memset(vis, 0 , sizeof vis );
	priority_queue< pair<int,int> ,vector< pair<int,int> > ,greater< pair<int,int> > > q;
	q.push(mp(0,m*n+s));
	dis[m*n+s] = 0;
	while(!q.empty()){
		int u, v, w;
		u=q.top().second; q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i = head[u]; i != -1; i = e[i].next){
			v=e[i].to, w=e[i].w;
			if(dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				q.push(mp(dis[v],v));
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m >> s >> t;
	memset(head,-1,sizeof(head));
	for(int i = 0; i < m; i++){
		int a, b ,c;
		cin >> a >> b >> c;
		int u, v;
		for(int j = 0; j < c ; j++){
			cin >> v;
			if(j){
				addEdge(i*n+u,i*n+v,b);
				addEdge(i*n+v,i*n+u,b);
			}
			addEdge(i*n+v, m*n+v, 0);
			addEdge(m*n+v, i*n+v, a);
			u = v;
		}
	}
	Dijsktra();
	ll res=dis[m*n+t];
	if(res >= INF) res = -1;
	cout << res << endl;
	return 0;
}