计蒜客 百度地图导航(Dijkstra&超级源点与超级汇点)

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

地图中有两类道路。第一类道路是 城市之间的快速路，两个城市 u,v 之间增加一条距离为 c 的边；第二类道路是 城市群之间的高速路，连接两个城市群 a,b，通过这条高速路，城市群 a 里的每个城市与城市群 b 里的每个城市之间两两增加一条距离为 c 的边。图中所有边均为无向边。
计算从城市 s 到城市 的最短路。

这道题思路很明了，建好图单源最短路跑一遍就可以了，但是关键在于建图。城市与城市之间的边很好建，直接加上去。但是如果建城市群的边的话就会比较麻烦，要写个二重循环，一一对应加边，倘若一个城市群有u个城市另一个有v个，时间复杂度达到O(nm)是巨大的.所以要转变加边的思路.

如果有两个城市群uv，u种有abc三个城市，v中有def三个城市。按照一一对应的加边方法，建图如下：

随着城市群中城市数量的加多，边的对应关系会越来越复杂。所以我们用两个特殊点分别作为城市群的入点和出点。添加城市群的边只要更改这两个点就可以了（x进入y出去）
那么如何添加城市群的边呢？我们只要把u的出点指向v的入点，再把v的出点指向u的如电就行了
像这样，随着城市群里面的城市增加，优化效果是显而易见的。
但是我们添加了点，所以要为点编号，1-n是不可用的，所以我们把入点编为n+u，出点边为2n+u

//建图用了链式前向星
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdio>
#include<queue>
#pragma comment(linker, "/STACK:102400000,102400000")   //防止栈溢出
using namespace std;
const int maxn = 5e5;
const long long inf = 1e18;
int n,m,cnt,m1,m2;
int u,v,w,s,t,k,temp;
int head[maxn],vis[maxn];
long long dis[maxn];
vector<int>vec[maxn];
struct edge{
    int to,next;
    long long w;
}e[maxn*10];
struct node{
    long long dis;
    int pos;
    bool operator < (const node & a) const{
        return a.dis < dis;
    }
};
void addedge(int u,int v,long long w){  //加边函数
    e[++cnt].to = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}
priority_queue<node>q;  //优先队列
void dijkstra(int s){   //堆优化的Dijkstra
    dis[s] = 0;
    q.push((node){0,s});
    while(!q.empty()){
        node temp = q.top();
        q.pop();
        int x = temp.pos;
        if(vis[x])  continue;
        vis[x] = 1;
        for(int i = head[x];i;i=e[i].next){
            int y = e[i].to;
            if(dis[y] > dis[x] + e[i].w){
                dis[y] = dis[x] + e[i].w;
                if(!vis[y]) q.push((node){dis[y],y});
            }
        }
    }

}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 0;i <= 2*n+m;i++)
        dis[i] = inf;
    for(int i = 1;i <= m;i++){
        scanf("%d",&k);
        while(k--){ //用vector存城市群
            scanf("%d",&temp);
            vec[i].push_back(temp);
        }
    }
    for(int i = 1;i <= m;i++){  //这是为城市群添加入点和出点
        for(int j = 0;j < vec[i].size();j++){
            addedge(i+n,vec[i][j],0);
            addedge(vec[i][j],i+2*n,0);
        }
    }
    scanf("%d",&m1);
    while(m1--){
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,w);
    }
    scanf("%d",&m2);
    while(m2--){    //为城市群加边
        scanf("%d%d%d",&u,&v,&w);
        addedge(v+2*n,u+n,w);
        addedge(u+2*n,v+n,w);
    }

    scanf("%d%d",&s,&t);    //起点和终点
    dijkstra(s);
    printf("%lld\n",(dis[t]>=inf?-1:dis[t]));
    return 0;
}