题目：

百度地图上有 nn 个城市，城市编号依次为 11 到 nn。地图中有若干个城市群，编号依次为 11 到 mm。每个城市群包含一个或多个城市；每个城市可能属于多个城市群，也可能不属于任何城市群。

地图中有两类道路。第一类道路是 城市之间的快速路，两个城市 u,vu,v 之间增加一条距离为 cc 的边；第二类道路是 城市群之间的高速路，连接两个城市群 a,ba,b，通过这条高速路，城市群 aa 里的每个城市与城市群 bb 里的每个城市之间两两增加一条距离为 cc 的边。图中所有边均为无向边。

你需要计算从城市 ss 到城市 tt 的最短路。

输入格式

第一行输入 n(1≤n≤20000),n(1≤n≤20000), m(0≤m≤20000)m(0≤m≤20000)，分别表示城市总数和城市群总数。

接下来一共输入 mm 行。

第 ii 行首先输入一个 ki(1≤ki≤n)k​i​​(1≤k​i​​≤n)，表示第 ii 个城市群中的城市数为 kik​i​​。接下来输入 kik​i​​ 个数，表示第 ii 个城市群中每个城市的编号（保证一个城市群内的城市编号不重复且合法，∑i=1mki≤20000∑​i=1​m​​k​i​​≤20000）。

下一行输入一个整数 m1(0≤m1≤20000)m​1​​(0≤m​1​​≤20000)，表示有 m1m​1​​ 条第一类道路，即 城市之间的快速路。

接下来 m1m​1​​ 行，每行输入三个整数 ui,vi(1≤ui,vi≤n),ci(1≤ci≤106)u​i​​,v​i​​(1≤u​i​​,v​i​​≤n),c​i​​(1≤c​i​​≤10​6​​)，分别表示快速路连接的两个城市编号和边的距离。

下一行输入一个整数 m2(0≤m2≤20000)m​2​​(0≤m​2​​≤20000)，表示有 m2m​2​​ 条第二类道路，即 城市群之间的高速路。

接下来 m2m​2​​ 行，每行输入三个整数 ai,bi(1≤ai,bi≤m),li(1≤li≤106)a​i​​,b​i​​(1≤a​i​​,b​i​​≤m),l​i​​(1≤l​i​​≤10​6​​)，分别表示快速路连接的两个城市群编号和边的距离。

最后一行输入 s,t(1≤s,t≤n)s,t(1≤s,t≤n)，表示起点和终点城市编号。

输出格式

输出一个整数，表示城市 ss 到城市 tt 到最短路。如果不存在路径，则输出-1。

样例说明

1 -> 2 - > 5或者1 -> 4 -> 5是最短的路径，总长度为 1212。

样例输入

5 42 5 12 2 41 32 3 421 2 91 5 1821 2 61 3 101 5

样例输出

12

 

 

                                                                                                                                       C 语言                                                                                                                                                                        C++ 语言 (C++11)                                                                                                                                                                        Java 语言                                                                                                                                                                        Python 语言 (2.7)                                                                                                                                                                        Ruby 语言                                                                                                                                                                        C++ 语言 (C++14)                                                                                                                                                                        Python 语言 (3.5)                                                                                              

 

 

 

 

 

题解：

把城市群看成一个点，然后对于城市群u里面的所有点，将其与u连接(双向边)

貌似很完美！

其实不行，对于一个城市群里面的两个城市，这么做以后，这两个城市就能够直接相通了！

下面用经典的拆点方法：

 

官方题解：

 

 

这样做对于每个城市群s，出点s2可以通过内部点到达s1，从而实现各个城市群的相通

而内部的城市只能到达s1，只能由s2到达，而s1无法到达s2，限制内部点直接相互到达。

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define rep(i,a,n) for (int i=a;i
            
             =a;i--)#define pb push_back#define fi first#define se secondtypedef vector
             
               VI;typedef long long ll;typedef pair
              
                PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=6e4+100;int head[maxn];struct edge{ int to,next; ll w;}e[maxn*20]; //int tol=0;void add(int u,int v,ll w){ e[++tol].to=v,e[tol].next=head[u],e[tol].w=w,head[u]=tol;}ll d[maxn];int inq[maxn],q[maxn];void spfa(int u){ rep(i,1,maxn) d[i]=1e18; memset(q,0,sizeof(q)); memset(inq,0,sizeof(inq)); inq[u]=1; d[u]=0; int front=0,rear=0; q[rear++]=u; while(front!=rear) { int x=q[front++]; inq[x]=0; if(front>=maxn) front=0; for(int i=head[x];i;i=e[i].next) { int v=e[i].to; if(d[x]+e[i].w
               
                =maxn) rear=0; } } }}int main(){ int n,m; scanf("%d%d",&n,&m); rep(i,1,m+1) { int v; scanf("%d",&v); while(v--) { int u; scanf("%d",&u); add(u,n+i,0),add(n+m+i,u,0); } } int m1; scanf("%d",&m1); while(m1--) { int u,v; ll w; scanf("%d%d%lld",&u,&v,&w); add(u,v,w),add(v,u,w); } scanf("%d",&m1); while(m1--) { int u,v; ll w; scanf("%d%d%lld",&u,&v,&w); add(n+u,m+n+v,w),add(n+v,m+n+u,w); } int s,t; scanf("%d%d",&s,&t); spfa(s); //printf("%d %d\n",s,t); if(d[t]==1e18) puts("-1"); else printf("%lld\n",d[t]); return 0;}