Luogu P1629 mail carrier

subject

Luogu P1629 mail carrier

analysis

It's easy to analyze the shortest path model by browsing the topic. First, run the shortest route from store 1 to other points, and then run the shortest route from each point when he returns. But in the process of returning, we only use the shortest route from each point to point 1, but we have to run (n-1) times, so it is obviously very wasteful. And the complexity is O(n*m log n), explosion.
How to solve this problem?
If we turn the direction of each side in the opposite direction, then the original shortest path from each point to 1 becomes the shortest path from 1 to each point, which is equivalent to that we go the way in the opposite direction. The answer is correct because the edge weights have not changed. So we transform the model of single source shortest circuit + single sink shortest circuit into two times single source shortest circuit!
It's also very convenient to realize. You only need to store each edge, first add the original edge when inputting, then run once to find the shortest path to each point, then empty the edge table and add the reverse edge, and then run once to find the shortest path when he comes back. Add up the two answers and it will be the final result. Time complexity is O(2*m log n). (using heap to optimize dijkstra)

code

#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=100002,inf=2147483647;
struct Edge{
    int to,next,v;
}e[maxn*2];
struct Node{
    int a,b;
    bool operator < (const Node &A) const
    {
        return b>A.b;
    }
};
int from[maxn],to[maxn],val[maxn],head[maxn],dis[maxn];
bool vis[maxn];
priority_queue<Node>q;
int n,m,cnt;
long long ans;
void add(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].v=w;
    head[u]=cnt;
}
void dijkstra()
{
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    dis[1]=0;
    q.push((Node){1,0});
    while(!q.empty())
    {
        Node u=q.top();
        q.pop();
        if(vis[u.a])    continue;
        vis[u.a]=1;
        for(int i=head[u.a];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]>dis[u.a]+e[i].v)
            {
                dis[v]=dis[u.a]+e[i].v;
                q.push((Node){v,dis[v]});
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&from[i],&to[i],&val[i]);
        add(from[i],to[i],val[i]);
    }
    dijkstra();
    for(int i=2;i<=n;i++)
        ans+=dis[i];
    memset(vis,0,sizeof(vis));
    memset(head,0,sizeof(head));
    cnt=0;
    //Don't forget to empty related variables and arrays!!
    for(int i=1;i<=m;i++)
        add(to[i],from[i],val[i]);
    dijkstra();
    for(int i=2;i<=n;i++)
        ans+=dis[i];
    printf("%lld",ans);
    return 0;
}

Added by cac818 on Sat, 30 May 2020 19:13:30 +0300