洛谷P1342 请柬

题目描述

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

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

输入输出格式

输入格式：

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

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

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

输出格式：

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

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

【注意】

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

/*
    正向建一个图，反向建一个图，跑两遍最短路即可，我用的SLF优化spfa
*/
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define maxn 1000010
using namespace std;
int n,m,num,head[maxn],num2,head2[maxn];
long long ans=0,dis[maxn];
bool vis[maxn];
struct node{
    int to,pre,v;
}e[maxn],e2[maxn];
void Insert(int from,int to,int v){
    e[++num].to=to;
    e[num].v=v;
    e[num].pre=head[from];
    head[from]=num;
}
void Insert2(int from,int to,int v){
    e2[++num2].to=to;
    e2[num2].v=v;
    e2[num2].pre=head2[from];
    head2[from]=num2;
}
void spfa1(){
    deque<int>q;q.push_back(1);
    for(int i=1;i<=n;i++)dis[i]=1234567890;
    memset(vis,0,sizeof(vis));
    vis[1]=1;dis[1]=0;
    while(!q.empty()){
        int now=q.front();q.pop_front();vis[now]=0;
        for(int i=head[now];i;i=e[i].pre){
            int to=e[i].to;
            if(dis[to]>dis[now]+e[i].v){
                dis[to]=dis[now]+e[i].v;
                if(!vis[to]){
                    vis[to]=1;
                    if(!q.empty()&&dis[to]<dis[q.front()])q.push_front(to);
                    else q.push_back(to);
                }
            }
        }
    }
    for(int i=2;i<=n;i++)ans+=dis[i];
}
void spfa2(){
    deque<int>q;q.push_back(1);
    for(int i=1;i<=n;i++)dis[i]=1234567890;
    memset(vis,0,sizeof(vis));
    vis[1]=1;dis[1]=0;
    while(!q.empty()){
        int now=q.front();q.pop_front();vis[now]=0;
        for(int i=head2[now];i;i=e2[i].pre){
            int to=e2[i].to;
            if(dis[to]>dis[now]+e2[i].v){
                dis[to]=dis[now]+e2[i].v;
                if(!vis[to]){
                    vis[to]=1;
                    if(!q.empty()&&dis[to]<dis[q.front()])q.push_front(to);
                    else q.push_back(to);
                }
            }
        }
    }
    for(int i=2;i<=n;i++)ans+=dis[i];
}
int main(){
    freopen("Cola.txt","r",stdin);
    scanf("%d%d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        Insert(x,y,z);Insert2(y,x,z);
    }
    spfa1();
    spfa2();
    cout<<ans;
}