luogu P1342 请柬

题目描述

在电视时代,没有多少人观看戏剧表演。Malidinesia古董喜剧演员意识到这一事实，他们想宣传剧院,尤其是古色古香的喜剧片。他们已经打印请帖和所有必要的信息和计划。许多学生被雇来分发这些请柬。每个学生志愿者被指定一个确切的公共汽车站，他或她将留在那里一整天,邀请人们参与。

这里的公交系统是非常特殊的:所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。学生每天早上从总部出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候,所有的学生都回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。

输入输出格式

输入格式：

第1行有两个整数n、m(1<=n,m<=1000000)，n是站点的个数，m是线路的个数。

然后有m行，每行描述一个线路，包括3个整数，起始点，目的地和价格。

总部在第1个站点，价钱都是整数，且小于1000000000。

输出格式：

输出一行，表示最小费用。

输入输出样例

输入样例#1：

输出样例#1：

说明

【注意】

此题数据规模较大，需要使用较为高效的算法，此题不设小规模数据分数。

由于数据较大，不可简单spfa：全TLE

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>

#define ll long long

using namespace std;
const int N=1000010;
const int Maxn=1000000010;

ll head[N];
ll now=1;
ll dis[N];
bool vis[N];
struct node{
    int u,v,w,nxt;
}E[N];
queue<int>q;
ll n,m;
ll answer;

inline ll read()
{
    ll x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}

inline void add(int u,int v,int w)
{
    E[now].v=v;
    E[now].w=w;
    E[now].nxt=head[u];
    head[u]=now++;
}

inline void spfa(int start)
{
    for(int i=1;i<=n;i++)
        dis[i]=Maxn;
    dis[start]=0;
    vis[start]=1;
    q.push(start);
    while(!q.empty())
    {
        int top=q.front();
        q.pop();
        vis[top]=0;
        for(int i=head[top];i!=-1;i=E[i].nxt)
            if(dis[E[i].v]>dis[top]+E[i].w)
            {
                dis[E[i].v]=dis[top]+E[i].w;
                if(!vis[E[i].v])
                {
                    vis[E[i].v]=1;
                    q.push(E[i].v);
                }
            }
    }
}

int main()
{
    n=read();
    m=read();
    
    for(int i=1;i<=n;i++)
        head[i]=-1;
        
    for(int i=1;i<=m;i++)
    {
        int u=read();
        int v=read();
        int w=read();
        add(u,v,w);
    }
    spfa(1);
    for(int i=2;i<=n;i++)
        answer+=dis[i];
    for(int i=2;i<=n;i++)
    {
        spfa(i);
        answer+=dis[1];
    }
    printf("%lld",answer);
    return 0;
}

存两次图，正反跑spfa：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>

#define ll long long

using namespace std;
const int N=1000010;
const int Maxn=100000010;

ll head[N];
ll head_2[N];
ll now=1;
ll now2=1;
ll dis[N];
ll dis_2[N];
bool vis[N];
struct node{
    int u,v,w,nxt;
}E[N];
struct NODE{
    int u,v,w,nxt;
}EE[N];
queue<int>q;
ll n,m;
ll answer;

inline ll read()
{
    ll x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}

inline void add(int u,int v,int w)
{
    E[now].v=v;
    E[now].w=w;
    E[now].nxt=head[u];
    head[u]=now++;
}

inline void add_2(int u,int v,int w)
{
    EE[now2].v=v;
    EE[now2].w=w;
    EE[now2].nxt=head_2[u];
    head_2[u]=now2++;
}

inline void spfa(int start)
{
    for(int i=1;i<=n;i++)
        dis[i]=Maxn;
    dis[start]=0;
    vis[start]=1;
    q.push(start);
    while(!q.empty())
    {
        int top=q.front();
        q.pop();
        vis[top]=0;
        for(int i=head[top];~i;i=E[i].nxt)
            if(dis[E[i].v]>dis[top]+E[i].w)
            {
                dis[E[i].v]=dis[top]+E[i].w;
                if(!vis[E[i].v])
                {
                    vis[E[i].v]=1;
                    q.push(E[i].v);
                }
            }
    }
}

inline void spfa_2(int start)
{
    for(int i=1;i<=n;i++)
        dis_2[i]=Maxn;
    dis_2[start]=0;
    vis[start]=1;
    q.push(start);
    while(!q.empty())
    {
        int top=q.front();
        q.pop();
        vis[top]=0;
        for(int i=head_2[top];~i;i=EE[i].nxt)
            if(dis_2[EE[i].v]>dis_2[top]+EE[i].w)
            {
                dis_2[EE[i].v]=dis_2[top]+EE[i].w;
                if(!vis[EE[i].v])
                {
                    vis[EE[i].v]=1;
                    q.push(EE[i].v);
                }
            }
    }
}

int main()
{
    n=read();
    m=read();
    
    for(int i=1;i<=n;i++)
        head[i]=-1,head_2[i]=-1;
        
    for(int i=1;i<=m;i++)
    {
        int u=read();
        int v=read();
        int w=read();
        add(u,v,w);
        add_2(v,u,w);
    }
    spfa(1);
    spfa_2(1);
    for(int i=1;i<=n;i++)
        answer+=(dis[i]+dis_2[i]);
    printf("%lld",answer);
    return 0;
}