Luogu

BZOJ

LOJ

分析

考虑一条 $u$ 到 $v$ 的最短路是怎么构成的。

显然会存在一条边 $(x,y)$ ,使得 $u\to v$ 的最短路由 $u\to x$ 的最短路、$(x,y)$ 和 $y\to v$ 的最短路构成。

那么先以所有关键点为源点,跑一遍 $\mathrm{dijkstra}$ ,并记录每个点的最短路是从哪个关键点出发的。

然后再在反图上跑一遍 $\mathrm{dijkstra}$ ,当找到一条边 $(u,v)$ 使得 $u$ 和 $v$ 不从同一个关键点扩展而来时,更新答案。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;
typedef long long ll;

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

const int N=100000+10;
const int M=500000+10;

int n,m,k;
int a[N];

struct Edge { int v,w,nxt; } e[M],fe[M];
int head[N],fhead[N],cnt=0,fcnt=0;

inline void addEdge(int u,int v,int w) {
    e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}

inline void faddEdge(int u,int v,int w) {
    fe[++fcnt]=(Edge){v,w,fhead[u]},fhead[u]=fcnt;
}

struct node { int u; ll d; };
bool operator <(node a,node b) { return a.d>b.d; }

priority_queue<node> Q,fQ;
ll dis[N],fdis[N],ans;
int from[N];

inline void dijkstra() {    
    for (re int i=1;i<=n;++i) dis[i]=2e18,from[i]=0;
    for (re int i=1;i<=k;++i) dis[a[i]]=0,from[a[i]]=a[i],Q.push((node){a[i],0});
    while (!Q.empty()) {
        node tp=Q.top(); Q.pop();
        int u=tp.u; ll d=tp.d;
        if (d!=dis[u]) continue;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (dis[u]+w<dis[v])
                dis[v]=dis[u]+w,from[v]=from[u],Q.push((node){v,dis[v]});
        }
    }
}

inline void fdijkstra() {
    for (re int i=1;i<=n;++i) fdis[i]=2e18;
    for (re int i=1;i<=k;++i) fdis[a[i]]=0,fQ.push((node){a[i],0});
    while (!fQ.empty()) {
        node tp=fQ.top(); fQ.pop();
        int u=tp.u; ll d=tp.d;
        if (d!=fdis[u]) continue;
        for (re int i=fhead[u];i;i=fe[i].nxt) {
            int v=fe[i].v,w=fe[i].w;
            if (from[u]!=from[v]) ans=min(ans,fdis[u]+w+dis[v]);
            if (fdis[u]+w<fdis[v])
                fdis[v]=fdis[u]+w,fQ.push((node){v,fdis[v]});
        }
    }
}

int main() {
    int T=read();
    while (T--) {
        memset(head,0,sizeof(head)),cnt=0;
        memset(fhead,0,sizeof(fhead)),fcnt=0;
        n=read(),m=read(),k=read();
        for (re int i=1;i<=m;++i) {
            int u=read(),v=read(),w=read();
            addEdge(u,v,w),faddEdge(v,u,w);
        }
        for (re int i=1;i<=k;++i) a[i]=read();
        ans=2e18; dijkstra(); fdijkstra();
        printf("%lld\n",ans);
    }
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 20 PM