UVA721 Invitation Cards（SPFA，反向建图技巧）

· · 题解

UVA721 Invitation Cards

反向建图是一种非常重要的解题思想，务必掌握.

题目描述

给定一张图，求从源点1到每个点的最短路之和和每个点到源点1的最短路之和的和. 保证整张图强连通，答案在int范围内.

题目分析

求源点1到每个点的最短路之和的做法是显然的.

而求每个点到源点的最短路，最直观的思路是直接每个点进行一次求最短路，但是观察数据范围，发现数据是百万级的，明显时间复杂度不满足.

我们考虑每个点到源点1的最短路. 可以发现，就算我们对每个点进行一次求最短路，实际上也只有到源点的数据派的上用场. 反过来想，源点到每个点的数据都是有用的，那么我们考虑从源点再做一次最短路. 由于之前的终点—源点变成了起点，所以要反向建图. 这样再跑一次最短路，求得的dis就是每个点到源点的最短路了.

考虑使用什么算法. 观察最极端的数据，发现1<=n,m<=1,000,000，也就是说，极大数据是一张稀疏图，稀疏图上采用O(km)的spfa算法较优；又因为堆优化dijkstra算法复杂度为O((n+m)log\:m)，极端情况下大约为(2*10^6)*20=4*10^7左右，时间复杂度比较悬，所以采用spfa算法实现最短路.

程序实现

//小写字母表示原图，大写字母表示反图
#include<bits/stdc++.h>
#define maxn 1000010
#define inf 0x3f3f3f3f
using namespace std;
struct edge{
    int v,w,next;
}e[maxn],E[maxn];
int head[maxn],tot1;
void add(int u,int v,int w){
    e[++tot1].v =v;
    e[tot1].w =w;
    e[tot1].next =head[u];
    head[u]=tot1;
}
int Head[maxn],tot2;
void Add(int u,int v,int w){
    E[++tot2].v =v;
    E[tot2].w =w;
    E[tot2].next =Head[u];
    Head[u]=tot2;
}
int dis[maxn];
bool vis[maxn];
void spfa(){
    memset(dis,inf,sizeof dis);
    memset(vis,false ,sizeof vis);
    dis[1]=0;
    vis[1]=true;
    queue<int >q;
    q.push(1);
    while(!q.empty()){
        int u=q.front();
        for(int i=head[u];i;i=e[i].next ){
            int v=e[i].v ;
            if(dis[v]>dis[u]+e[i].w ){
                dis[v]=dis[u]+e[i].w ;
                if(!vis[v]){
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
        vis[u]=false;
        q.pop();
    }
}
int Dis[maxn];
void Spfa(){
    memset(Dis,inf,sizeof Dis);
    memset(vis,false,sizeof vis);
    Dis[1]=0;
    vis[1]=true;
    queue<int >q;
    q.push(1);
    while(!q.empty()){
        int u=q.front();
        for(int i=Head[u];i;i=E[i].next ){
            int v=E[i].v ;
            if(Dis[v]>Dis[u]+E[i].w ){
                Dis[v]=Dis[u]+E[i].w ;
                if(!vis[v]){
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
        vis[u]=false;
        q.pop();
    }
}
int n,m,ans;
int main(){
    int T;
    scanf("%d",&T);
    for(int ab=1;ab<=T;ab++){
        memset(e,0,sizeof e);
        memset(head,0,sizeof head);
        memset(E,0,sizeof E);
        memset(Head,0,sizeof Head);
        ans=0;//初始化要彻底，不要残留数据
        scanf("%d%d",&n,&m);
        for(int i=1,u,v,w;i<=m;i++){
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            Add(v,u,w);
        }
        spfa();
        Spfa();
        for(int i=1;i<=n;i++){
            ans+=(dis[i]+Dis[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}