题解 P1342 【请柬】

· · 题解

一道关于Dij+堆优化的最短路的问题。（废话）

看见其他大佬都用的前式链向星和priority_queue自定义比较器，没有用vector的，所以我来发一篇vector和STL的题解。

首先来了解一下Dij，Dij是求求最短路时比较快的一种方法，思路简单，但也有一个缺点，那就是无法判权值为负的情况。

Dij加堆优化讲解

这道题就是让我们先求一遍1到所有点的最短距离，再求一遍从各个点到1的最短距离，再将值都加起来，就是最终答案。

看似简单，相信在求每个点到1的最短路时，第一个想到的，肯定是一个for，循环每一个点，求一遍Dij，在把所有的d[1]加起来。

恭喜您，丰收了4个TLE

那我们来思考一下正解，我们可以把图正着存一遍，然后再反着存一遍，分别求Dij(1)。

正着的图求出来的遗爱到每个点的距离，及所有人出发到每个点的费用；

反着存图，求出来的也是1到每个点的最短路，但这张图是反着的，举个例子：反着的图中1到6的值在正着的图中就是6到1的最短路。所以，反着的图到每个点的距离就是正着的图中每个点到1的距离。

这样我们就可以大大缩短时间，从而求得正解。

#include<bits/stdc++.h>
using namespace std;
#define si 1000009
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
struct edge
{
    int to,cost;
};
int INF=2147483647;
typedef pair<long long,long long> P;
vector<edge> g[si];
vector<edge> g2[si];
int d[si];
priority_queue<P, vector<P>, greater<P> > q;
int n,m,a,b,c;
long long ans;
void dij(int x)
{
    fill(d,d+1+n,INF);
    d[x]=0;
    q.push(P(0,x));
    while(!q.empty())
    {
        P p=q.top();q.pop();
        int v=p.second;
        if(d[v]<p.first) continue;
        for(int i=0;i<g[v].size();i++)
        {
            edge e=g[v][i];
            if(d[e.to]>d[v]+e.cost)
            {
                d[e.to]=d[v]+e.cost;
                q.push(P(d[e.to],e.to));
            }
        }
    }
}
void dij2(int x)
{
    fill(d,d+1+n,INF);
    d[x]=0;
    q.push(P(0,x));
    while(!q.empty())
    {
        P p=q.top();q.pop();
        int v=p.second;
        if(d[v]<p.first) continue;
        for(int i=0;i<g2[v].size();i++)
        {
            edge e=g2[v][i];
            if(d[e.to]>d[v]+e.cost)
            {
                d[e.to]=d[v]+e.cost;
                q.push(P(d[e.to],e.to));
            }
        }
    }
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        a=read();b=read();c=read();
        g[a].push_back(edge{b,c});
        g2[b].push_back(edge{a,c});
    }
    dij(1);
    for(int i=2;i<=n;i++)
    ans+=d[i];
    dij2(1);
    for(int i=2;i<=n;i++)
    ans+=d[i];
    cout<<ans;
    return 0;
}