LG-1629

有一个邮递员要送东西，邮局在节点 $1$。他总共要送 $n-1$ 样东西，其目的地分别是节点 $2$ 到节点 $n$。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 $m$ 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 $n-1$ 样东西并且最终回到邮局最少需要的时间。

思路

由于必须要返回邮局，所以不仅仅需要知道点 $1$ 到其他点的最短路，还要知道其他点到 $1$ 的最短路。

由于是单向边，思考一下，反着建图的话跑一遍 SPFA 不就是其他点到 $1$ 的最短路吗？

于是直接正向跑一遍 SPFA，反着跑一遍 SPFA，累加最短路即可。

这里学到一个反向建图的技巧，直接将反向图建在 $n+1$ 到 $n+n$ 点上。

代码

#include<bits/stdc++.h>
#define N 100010

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,m,ans=0;

int head[N<<1],tot=0;
struct graph{
    int v,w,next;
}edge[N<<1];
void add_edge(int u,int v,int w) {
    edge[++tot].v=v;
    edge[tot].w=w;
    edge[tot].next=head[u];
    head[u]=tot;
}

int dis[N<<1];
bool vh[N<<1];
queue<int> q;
void SPFA(int s) {
    memset(vh,0,sizeof(vh));
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push(s);
    vh[s]=true;
    while(!q.empty()) {
        int u=q.front();q.pop();
        vh[u]=false;
        for(int i=head[u];i;i=edge[i].next) {
            int v=edge[i].v,w=edge[i].w;
            if(dis[u]<dis[v]-w) {
                dis[v]=dis[u]+w;
                if(!vh[v]) {
                    q.push(v);
                    vh[v]=true;
                }
            }
        }
    }
}

int main() {
    n=read(),m=read();
    for(int i=1;i<=m;i++) {
        int u=read(),v=read(),w=read();
        add_edge(u,v,w),add_edge(v+n,u+n,w);
    }
    SPFA(1);
    for(int i=2;i<=n;i++) ans+=dis[i];
    SPFA(1+n);
    for(int i=2+n;i<=n+n;i++) ans+=dis[i];
    printf("%d\n",ans);
    system("pause");
    return 0;
}