p1342 invitation
P1342

Reverse mapping of the shortest path (invitation)

Topic background

In the age of television, not many people watch plays. Malidinesia antique comedians are aware of this fact, and they want to promote the theater, especially antique comedies.

Title Description

They have printed out the invitation and all necessary information and plans. Many students were hired to distribute these invitations. Each student volunteer is assigned an exact bus stop where he or she will stay all day and invite people to participate.

The bus system here is very special: shared n n n sites and m m m lines, all of which are unidirectional, connecting two stations. The bus leaves the starting point and returns to the starting point empty after arriving at the destination.

Students from the 1 1 Starting from station 1, take a bus to a scheduled station to invite passengers. Each site is assigned a student. At the end of the day, all the students returned to the headquarters. What we need to know now is what is the minimum total bus cost for students.

Input format

The first line of input is two integers, representing the number of sites n n n and number of lines m m m.

Section 2 2 2 to ( m + 1 ) (m + 1) (m+1) lines, three integers per line u , v , w u, v, w u. V, W, stands for the existence of a u u u departure arrival v v v at a cost of w w w.

Output format

Output an integer per line, indicating the minimum cost.

Example \1

Sample input \1

4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

Sample output \1

210

Tips

Data scale and agreement

about 100 % 100\% 100% data to ensure:

• 1 ≤ n , m ≤ 1 0 6 1 \leq n, m \leq 10^6 1≤n,m≤106.
• 1 ≤ u , v ≤ n 1 \leq u, v \leq n 1≤u,v≤n， 1 ≤ w ≤ 1 0 9 1 \leq w \leq 10^9 1≤w≤109.
• from 1 1 All stations can be reached after departure.

Idea: reverse mapping. head1 is a positive one from 1 to other points, and head2 is a positive one from other points to 1

#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <queue>
#define ll long long 
using namespace std;
const int maxn=1e6+10;
const ll inf=1e18;
ll dis[maxn];
bool vis[maxn];
int n,m,head1[maxn<<2],head2[maxn<<2],cnt1,cnt2;
struct edge 
{
    int next,to,w;
}e1[maxn<<2],e2[maxn<<2];
struct node
{
    int pos,dis;
    friend bool operator <(const node x,const node y)
    {
        return x.dis>y.dis;
    }
};
priority_queue<node>q;
void add (int f,int u,int v,int w)
{
    if (f==1)
    {
        e1[++cnt1].next=head1[u];
        e1[cnt1].to=v;
        e1[cnt1].w=w;
        head1[u]=cnt1;
        return ;
    }
    else if (f==2)
    {
        e2[++cnt2].next=head2[u];
        e2[cnt2].to=v;
        e2[cnt2].w=w;
        head2[u]=cnt2;
        return ;
    }
}
void dijkstra (int *head,edge *e,int s)
{
    for (int i=1;i<=n;i++)
    {
        dis[i]=inf;
        vis[i]=false;
    }
    node st,be,en;
    st.pos=s;
    st.dis=0;
    dis[s]=0;
    q.push(st);
    while (!q.empty())
    {
        be=q.top();
        q.pop();
        int u=be.pos;
        if (vis[u]) continue ;
        vis[u]=true;
        for (int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            int w=e[i].w;
            if (dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                en.dis=dis[v];
                en.pos=v;
                q.push(en);
            }
        }
    }
    return ;
}
int main ()
{
    scanf ("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf ("%d%d%d",&u,&v,&w);
        add(1,u,v,w);
        add(2,v,u,w);
    }
    dijkstra(head1,e1,1);
    ll ans=0;
    for (int i=1;i<=n;i++)
    {
        ans+=dis[i];
    }
    dijkstra(head2,e2,1);
    for (int i=1;i<=n;i++)
    {
        ans+=dis[i];
    }
    printf ("%lld\n",ans);
    system("pause");
    return 0;
}