百度地图上有 nn 个城市，城市编号依次为 11 到 nn。地图中有若干个城市群，编号依次为 11 到 mm。每个城市群包含一个或多个城市；每个城市可能属于多个城市群，也可能不属于任何城市群。
地图中有两类道路。第一类道路是 城市之间的快速路，两个城市 u,vu,v 之间增加一条距离为 cc 的边；第二类道路是 城市群之间的高速路，连接两个城市群 a,ba,b，通过这条高速路，城市群 aa 里的每个城市与城市群 bb 里的每个城市之间两两增加一条距离为 cc 的边。图中所有边均为无向边。
你需要计算从城市 ss 到城市 tt 的最短路。
输入格式
第一行输入 n(1 le n le 20000),n(1≤n≤20000), m(0 le m le 20000)m(0≤m≤20000)，分别表示城市总数和城市群总数。
接下来一共输入 mm 行。
第 ii 行首先输入一个 k_i(1 le k_i le n)ki(1≤ki≤n)，表示第 ii 个城市群中的城市数为 k_iki。接下来输入 k_iki 个数，表示第 ii 个城市群中每个城市的编号（保证一个城市群内的城市编号不重复且合法，sum_{i=1}^{m}k_i le 20000∑i=1mki≤20000）。
下一行输入一个整数 m_1(0 le m_1 le 20000)m1(0≤m1≤20000)，表示有 m_1m1 条第一类道路，即 城市之间的快速路。
接下来 m_1m1 行，每行输入三个整数 u_i,v_i(1 le u_i, v_i le n),c_i(1 le c_i le 10^6)ui,vi(1≤ui,vi≤n),ci(1≤ci≤106)，分别表示快速路连接的两个城市编号和边的距离。
下一行输入一个整数 m_2(0 le m_2 le 20000)m2(0≤m2≤20000)，表示有 m_2m2 条第二类道路，即 城市群之间的高速路。
接下来 m_2m2 行，每行输入三个整数 a_i,b_i(1 le a_i, b_i le m),l_i(1 le l_i le 10^6)ai,bi(1≤ai,bi≤m),li(1≤li≤106)，分别表示快速路连接的两个城市群编号和边的距离。
最后一行输入 s, t(1 le s, t le n)s,t(1≤s,t≤n)，表示起点和终点城市编号。
输出格式
输出一个整数，表示城市 ss 到城市 tt 到最短路。如果不存在路径，则输出-1。
样例说明
1 -> 2 - > 5或者1 -> 4 -> 5是最短的路径，总长度为 1212。
样例输入
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
比起普通的最短路问题多了一个“城市群”的概念，本题的关键也就是在于处理城市群这一情况。暴力的将两两城市群中城市分别连边会造成MLE（感觉也会TLE）。实际上可以通过拆点的方法将一个城市群转化为2个点。一个点作为城市群的“入口”连向城市群中所有的城市，一个点作为城市群的“出口”由城市群中所有城市连向。这两类边权值为0，城市群之间的距离通过一个城市的出口连另一个城市的入口表示。之后直接运行一遍dijkstra即可。
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <queue> 8 #include <set> 9 #include <map> 10 #include <list> 11 #include <vector> 12 #include <stack> 13 #define mp make_pair 14 //#define P make_pair 15 #define MIN(a,b) (a>b?b:a) 16 //#define MAX(a,b) (a>b?a:b) 17 typedef long long ll; 18 typedef unsigned long long ull; 19 const int MAX=6e4+5; 20 const int MAX_V=6e4+5; 21 const ll INF=2e11+5; 22 //const double M=4e18; 23 using namespace std; 24 //const int MOD=1e9+7; 25 typedef pair<ll,int> pii; 26 const double eps=0.000000001; 27 #define rank rankk 28 struct edge 29 { 30 int from,to,dis; 31 edge(int u,int v,int d):from(u),to(v),dis(d){} 32 }; 33 struct HeapNode 34 { 35 ll d; 36 int u; 37 bool operator <(const HeapNode &rhs)const 38 { 39 return d>rhs.d; 40 } 41 }; 42 struct Dijkstra 43 { 44 int n,m; 45 vector<edge> edges; 46 vector<int>G[MAX]; 47 bool done[MAX]; 48 ll d[MAX]; 49 int p[MAX]; 50 void init(int n) 51 { 52 this->n=n; 53 for(int i=1;i<=n;i++) 54 G[i].clear(); 55 edges.clear(); 56 } 57 void Addedge(int from,int to,int dist) 58 { 59 edges.push_back(edge(from,to,dist)); 60 m=edges.size(); 61 G[from].push_back(m-1); 62 } 63 void dijkstra(int s) 64 { 65 priority_queue<HeapNode>Q; 66 for(int i=1;i<=n;i++) 67 d[i]=INF; 68 d[s]=0; 69 memset(done,false,sizeof(done)); 70 Q.push((HeapNode){0,s}); 71 while(!Q.empty()) 72 { 73 HeapNode x=Q.top();Q.pop(); 74 int u=x.u; 75 if(done[u]) 76 continue; 77 done[u]=true; 78 for(int i=0;i<G[u].size();i++) 79 { 80 edge &e=edges[G[u][i]]; 81 if(d[e.to]>d[u]+e.dis) 82 { 83 d[e.to]=d[u]+e.dis; 84 p[e.to]=G[u][i]; 85 Q.push((HeapNode){d[e.to],e.to}); 86 } 87 } 88 } 89 } 90 }; 91 int n,m; 92 int main() 93 { 94 scanf("%d%d",&n,&m); 95 Dijkstra o; 96 o.n=n+2*m;o.m=0; 97 for(int i=1;i<=m;i++) 98 { 99 int num; 100 scanf("%d",&num); 101 for(int j=1;j<=num;j++) 102 { 103 int to; 104 scanf("%d",&to); 105 o.Addedge(n+i,to,0); 106 o.Addedge(to,n+i+m,0); 107 } 108 } 109 int m1; 110 scanf("%d",&m1); 111 for(int i=1;i<=m1;i++) 112 { 113 int u,v,t; 114 scanf("%d%d%d",&u,&v,&t); 115 o.Addedge(u,v,t); 116 o.Addedge(v,u,t); 117 } 118 int m2; 119 scanf("%d",&m2); 120 for(int i=1;i<=m2;i++) 121 { 122 int u,v,t; 123 scanf("%d%d%d",&u,&v,&t); 124 o.Addedge(n+u+m,n+v,t); 125 o.Addedge(n+v+m,n+u,t); 126 } 127 int s,t; 128 scanf("%d%d",&s,&t); 129 o.dijkstra(s); 130 printf("%lld ",o.d[t]==INF?-1LL:o.d[t]); 131 return 0; 132 }