Luogu

LOJ

做法一

将所有关键点随机分到两组中，然后新建两个点 $s,t$，从 $s$ 向第一组中所有点连 $0$ 边，从第二组中所有点向 $t$ 连 $0$ 边，求 $s$ 到 $t$ 的最短路即可。这样子的正确率大概是 $\frac{1}{4}$，所以我们只要多做几次就可以过了。

代码没有。

做法二

分析

事实上没有必要随机。我们枚举二进制位 $i$，将所有不含这个二进制位的关键点放到第一组，含这个二进制位的点放到第二组，套用上面的做法即可。因为答案的两个关键点一定有至少一个二进制位不同所以这样子是对的。需要注意的是因为是有向图所以要交换两组再做一次。

复杂度 $\mathcal{O}(n\log^2 n)$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;

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;

int n,m,k,key[N];
vector<pair<int,int> > G[N],E[N];

struct node { int u; ll d; };
bool operator <(node a,node b) { return a.d>b.d; }
ll dis[N];
void dijkstra(int s) {
    memset(dis,0x3f,sizeof(dis)); dis[s]=0;
    priority_queue<node> Q; Q.push((node){s,0});
    while (!Q.empty()) {
        int u=Q.top().u; ll d=Q.top().d; Q.pop();
        if (d!=dis[u]) continue;
        for (auto t:E[u]) { int v=t.fi,w=t.se;
            if (d+w<dis[v]) dis[v]=d+w,Q.push((node){v,d+w});
        }
    }
}

int main() {
    int T=read();
    while (T--) {
        n=read(),m=read(),k=read();
        for (int i=1;i<=n;++i) G[i].clear();
        for (int i=1;i<=m;++i) {
            int u=read(),v=read(),w=read();
            G[u].emplace_back(mp(v,w));
        }
        for (int i=1;i<=k;++i) key[i]=read();
        ll ans=5e18;
        for (int i=0;(1<<i)<=n;++i) {
            for (int j=1;j<=n;++j) E[j]=G[j];
            E[0].clear(),E[n+1].clear();
            for (int j=1;j<=k;++j) {
                if (key[j]&(1<<i)) E[0].emplace_back(mp(key[j],0));
                else E[key[j]].emplace_back(mp(n+1,0));
            }
            dijkstra(0); ans=min(ans,dis[n+1]);
            for (int j=1;j<=n;++j) E[j]=G[j];
            E[0].clear(),E[n+1].clear();
            for (int j=1;j<=k;++j) {
                if (key[j]&(1<<i)) E[key[j]].emplace_back(mp(n+1,0));
                else E[0].emplace_back(mp(key[j],0));
            }
            dijkstra(0); ans=min(ans,dis[n+1]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

做法三

分析

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

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

那么先以所有关键点为源点，跑一遍 Dijkstra，并记录每个点的最短路是从哪个关键点出发的。然后再在反图上跑一遍 Dijkstra，找到一条边 $(u,v)$ 使得 $u$ 和 $v$ 不从同一个关键点扩展而来时，更新答案。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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;

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

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];

void dijkstra() {   
    for (int i=1;i<=n;++i) dis[i]=2e18,from[i]=0;
    for (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 (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]});
        }
    }
}

void fdijkstra() {
    for (int i=1;i<=n;++i) fdis[i]=2e18;
    for (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 (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 (int i=1;i<=m;++i) {
            int u=read(),v=read(),w=read();
            addEdge(u,v,w),faddEdge(v,u,w);
        }
        for (int i=1;i<=k;++i) a[i]=read();
        ans=2e18; dijkstra(); fdijkstra();
        printf("%lld\n",ans);
    }
    return 0;
}