（最短路 SPFA）Invitation Cards -- poj -- 1511

链接：

http://poj.org/problem?id=1511

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82829#problem/J

代码：

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <vector>

#include <queue>

#include <map>

using namespace std;

#define N 1000005

#define oo 0x3fffffff

struct node

{

    int a, b, next;

    long long p;

}s1[N], s[N];

int n, m, head[N];

long long dis[N];

bool vis[N];

void Add(int a, int b, long long p, int k)

{

    s1[k].a=a;

    s1[k].b=b;

    s1[k].p=p;

    s1[k].next=head[a];

    head[a]=k;

}

long long spfa()

{

    queue<int>Q;

    Q.push();

    vis[]=true;

    for(int i=; i<=n; i++)

        dis[i]=oo;

    dis[]=;

    while(Q.size())

    {

        int i = Q.front(); Q.pop();

        vis[i] = false;

        for(int j=head[i]; j != ; j = s1[j].next)

        {

            int a = s1[j].a, b = s1[j].b;

            int p = s1[j].p;

            if(dis[a]+p < dis[b])

            {

                dis[b] = dis[a] + p;

                if(vis[b] == false)

                {

                    Q.push(b);

                    vis[b] = true;

                }

            }

        }

    }

    long long sum=;

    for(int i=; i<=n; i++)

        sum += dis[i];

    return sum;

}

int main()

{

    int t;

    scanf("%d", &t);

    while(t--)

    {

        scanf("%d%d", &n, &m);

        int i;

        memset(head, , sizeof(head));

        memset(s, , sizeof(s));

        memset(s1, , sizeof(s1));

        for(i=; i<=m; i++)

        {

            scanf("%d%d%I64d", &s[i].a, &s[i].b, &s[i].p);

            Add(s[i].a, s[i].b, s[i].p, i);

        }

        long long ans = spfa();

        memset(head, , sizeof(head));

        for(i=; i<=m; i++)

            Add(s[i].b, s[i].a, s[i].p, i);

        ans += spfa();

        printf("%I64d\n", ans);

    }

    return ;

}