题意
百度地图上有n个城市，城市编号依次为1到n。地图中有若干个城市群，编号依次为1到m。每个城市群包含一个或多个城市；
每个城市可能属于多个城市群，也可能不属于任何城市群。
地图中有两类道路。第一类道路是 城市之间的快速路，两个城市u,v之间增加一条距离为c的边；第二类道路是城市群之间的高速路，
连接两个城市群 a,b 通过这条高速路，城市群a里的每个城市与城市群b里的每个城市之间两两增加一条距离为c的边。
图中所有边均为无向边.你需要计算从城市s到城市t的最短路,如果不存在输出-1。
数据
第一行输入n(1 <= n <= 2e4), m(0 <= m <= 2e4)，分别表示城市总数和城市群总数。
接下来一共输入m行。
第i行首先输入一个k[i](1 <= k[i] <= n)表示第i个城市群中的城市数为k[i].
接下来输入k[i]个数，表示第i个城市群中每个城市的编号（保证一个城市群内的城市编号不重复且合法, 且所有k[i]总和不超过2e4。
下一行输入一个整数m1(0 <= m1 <= 2e4)，表示有m1条第一类道路，即 城市之间的快速路。
接下来 m1行，每行输入三个整数ui, vi(1 <= ui,vi <= n), ci(1 <= ci <= 1e6)，分别表示快速路连接的两个城市编号和边的距离。
下一行输入一个整数m2(0 <= m2 <= 2e4)，表示有 m2条第二类道路，即城市群之间的高速路。
接下来m2行，每行输入三个整数a[i], b[i](1 <= ai, bi <= m)，l[i](1 <= l[i] <= 1e6), 分别表示快速路连接的两个城市群编号和边的距离。
最后一行输入 s, t(1<= s, t <= n), s,t表示起点和终点城市编号。
输入
5 4
2 5 1
2 2 4
1 3
2 3 4
2
1 2 9
1 5 18
2
1 2 6
1 3 10
1 5
输出
12
题解：
对于城市以及城市之间的快速路，直接建边，
对每个城市群，新建一个入点和一个出点，城市群内的每个点向入点连一条有向边，出点向城市群内的每个点连一条有向边，
对于城市群之间的高速路，分别从两个城市群的入点向另一个城市群的出点连一条有向边，
这样点数和边数都是线性的，之后跑一次城市s到城市t的最短路即可。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define ls i<<1 #define rs ls | 1 #define mid ((ll+rr)>>1) #define pii pair<int,int> #define MP make_pair typedef long long LL; const long long INF = 1e18+1LL; const double Pi = acos(-1.0); const int N = 5e5+10, M = 1e3+20, mod = 1e9+7,inf = 2e8; int n,m,m1,m2,mi[N]; LL dist[N]; vector<int > G[N]; priority_queue<pair<LL,int> , vector<pair<LL,int> > , greater<pair<LL,int> > > q; struct ss{ int to,next; LL cost; }e[N * 10]; int head[N],t = 1; void add(int u,int v,int w) { e[t].next = head[u]; e[t].to = v; e[t].cost = w; head[u] = t++; } LL dij(int s,int t) { for(int i = 0; i <= n*2+m; ++i) dist[i] = INF; dist[s] = 0; q.push(MP(0,s)); while(!q.empty()) { pair<int,int > k = q.top(); q.pop(); int v = k.second; if(dist[v] < k.first) continue; for(int i = head[v]; i; i = e[i].next) { int to = e[i].to; if(dist[to] > dist[v] + e[i].cost) { dist[to] = dist[v] + e[i].cost; q.push(MP(dist[to],to)); } } } return dist[t] >= INF? -1: dist[t]; } int main() { scanf("%d%d",&n,&m); for(int i = 1; i <= m; ++i) { int x,y; scanf("%d",&x); for(int j = 1; j <= x; ++j) { scanf("%d",&y); G[i].push_back(y); } } scanf("%d",&m1); for(int i = 1; i <= m1; ++i) { int x,y,w; scanf("%d%d%d",&x,&y,&w); add(x,y,w); add(y,x,w); } scanf("%d",&m2); for(int i = 1; i <= m2; ++i) { int x,y,w; scanf("%d%d%d",&x,&y,&w); add(x+n,y+n*2,w); add(y+n,x+n*2,w); } for(int i = 1; i <= m; ++i) { for(int j = 0; j < G[i].size(); ++j) { int y = G[i][j]; add(y,i+n,0); add(i+n*2,y,0); } } int s,t; scanf("%d%d",&s,&t); printf("%lld ",dij(s,t)); return 0; }