poj1511InvitationCards

题意

题目给了一些站点。和一些路线(单向的)。现在有很多ACM志愿者,他们要从中央站点出发分别到其它站点

志愿者在傍晚还需要返回中央点(第一个点)。求最少所需的费用。

解法

两次spfa,第一次对原图spfa把中央检查站到每个站的距离相加,第二次对反图spfa,再把各站到中央检查站的距离相加,输出即可

//bnu1630
#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
#define MAX 1000006
struct G
{
    int s,e;
    long long v;
    int n;
}g[MAX],g2[MAX];
const long long INF=0xffffffff;
long long dis[MAX];
int first[MAX],vis[MAX];
int first2[MAX];
int tot,n,m,tot2;
int insert(int a,int b,int c)
{
    g[tot].s=a;
    g[tot].e=b;
    g[tot].v=(long long)c;
    g[tot].n=first[a];
    first[a]=tot++;
    return 0;
}
int insert2(int a,int b,int c)
{
    g2[tot2].s=a;
    g2[tot2].e=b;
    g2[tot2].v=(long long)c;
    g2[tot2].n=first2[a];
    first2[a]=tot2++;
    return 0;
}
int spfa(int s)
{
    deque<int>que;
    for(int i=0;i<=n;i++){
        dis[i]=INF;
        vis[i]=0;
    }   
    que.push_front(s);
    vis[s]=1;
    dis[s]=0;
    while(!que.empty())
    {
        int x=que.front();que.pop_front();
        for(int i=first[x];i!=-1;i=g[i].n)
            if(dis[g[i].e]>dis[x]+g[i].v)
            {
                dis[g[i].e]=dis[x]+g[i].v;
                if(!vis[g[i].e])
                {
                    if(dis[g[i].e]>dis[i])
                        que.push_back(g[i].e);
                    else
                        que.push_front(g[i].e);
                    vis[g[i].e]=1;
                }
            }
    }
    return 0;
}
int spfa2(int s)
{
    deque<int>que;
    for(int i=0;i<=n;i++)
    {
        dis[i]=INF;
        vis[i]=0;
    }
    que.push_front(s);
    vis[s]=1;
    dis[s]=0;
    while(!que.empty())
    {
        int x=que.front();que.pop_front();
        for(int i=first2[x];i!=-1;i=g2[i].n)
            if(dis[g2[i].e]>dis[x]+g2[i].v)
            {
                dis[g2[i].e]=dis[x]+g2[i].v;
                if(!vis[g2[i].e])
                {
                    if(dis[g2[i].e]>dis[i])
                        que.push_back(g2[i].e);
                    else
                        que.push_front(g2[i].e);
                    vis[g2[i].e]=1;
                }
            }
    }
    return 0;
}
int main()
{
    int ca,a,b,c;
    long long res;
    scanf("%d",&ca);
    while(ca--)
    {
        tot=0;
        res=0;
        memset(first,-1,sizeof(first));
        memset(first2,-1,sizeof(first2));
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            insert(a,b,c);
            insert2(b,a,c);
        }
        spfa(1);
        for(int i=2;i<=n;i++)   res+=dis[i];
        spfa2(1);
        for(int i=2;i<=n;i++)   res+=dis[i];;
        printf("%lld\n",res);
    }
    return 0;
}