Invitation Cards---poj1511（spfa）

有向图有n个点m条边，求点1到其他n-1个点的最短距离和+其他点到点1的最小距离和；

和poj3268一样，但是本题的数据范围较大，只能用spfa+邻接表写，不能用vector；

两个spfa即可；

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <map>
#include <string>
typedef long long LL;
///#define INF 0x3f3f3f3f
#define INF 100000000000000
#define N 1000100

using namespace std;

struct node
{
    int v;
    LL w;
    node(){};
    node(int v, LL w):v(v),w(w){}
};

vector<node > G[N];
vector<node > G1[N];

int vis[N], n, m;
LL dist[N];

LL spfa1(int s)
{
    for(int i=1; i<=n; i++)
        dist[i] = INF;
    dist[s] = 0;
    queue<int> Q;
    Q.push(s);
    memset(vis, 0, sizeof(vis));
    vis[s] = 1;
    while(!Q.empty())
    {
        int p = Q.front(); Q.pop();
        vis[p] = 0;
        for(int i=0, len=G[p].size(); i<len; i++)
        {
            node q = G[p][i];
            if(dist[q.v] > dist[p] + q.w)
            {
                dist[q.v] = dist[p] + q.w;
                if(!vis[q.v])
                {
                    vis[q.v] = 1;
                    Q.push(q.v);
                }
            }
        }
    }
    LL ans = 0;
    for(int i=1; i<=n; i++)
        ans += dist[i];
    return ans;
}

LL spfa2(int s)
{
    queue<int>Q;
    for(int i=1; i<=n; i++)
        dist[i] = INF;
    memset(vis, 0, sizeof(vis));
    vis[s] = 1;
    dist[s] = 0;
    Q.push(s);
    while(!Q.empty())
    {
        int p = Q.front(); Q.pop();
        vis[p] = 0;
        for(int i=0, len=G1[p].size(); i<len; i++)
        {
            node q = G1[p][i];
            if(dist[q.v] > dist[p] + q.w)
            {
                dist[q.v] = dist[p] + q.w;
                if(!vis[q.v])
                {
                    vis[q.v] = 1;
                    Q.push(q.v);
                }
            }
        }
    }
    LL ans = 0;
    for(int i=1; i<=n; i++)
        ans += dist[i];
    return ans;
}


int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d %d", &n, &m);
        for(int i=1; i<=n; i++)
        {
            G[i].clear();
            G1[i].clear();
        }
        for(int i=1; i<=m; i++)
        {
            int u, v; LL w;
            scanf("%d %d %I64d", &u, &v, &w);
            G[u].push_back(node(v, w));
            G1[v].push_back(node(u, w));
        }
        LL ans = spfa1(1);
        ans += spfa2(1);
        printf("%I64d
", ans);
    }
    return 0;
}

View Code