题意

给定一个有向图，其中一些顶点为关键点。求这些关键点两两之间最小距离。

题解

考试时没怎么想写了50分暴力走了。以为是什么强连通分量的解法，结果就是个最短路。直接从关键点跑一次最短路dis[0]，再把图反向在跑一次最短路dis[1]。跑最短路的时候记录起点col[0/1]。那么最后直接枚举一条边(x,y,w)，当col[0][x]!=col[1][y]时，答案一定在所有dis[0][x]+w+dis[1][y]中，取最小值即可。

相当于把路径拆成3部分。

CODE

#include <bits/stdc++.h>
using namespace std;
inline void read(int &x) {
    char ch; while(!isdigit(ch=getchar()));
    for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0');
}
typedef long long LL;
const int MAXN = 100005;
const int MAXM = 500005;
const LL inf = 1ll<<50;
int n, m, k, a[MAXN], fir[MAXN], to[MAXM], nxt[MAXM], wt[MAXM], cnt;
inline void link(int u, int v, int w) { if(u == v) return;
    to[++cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt; wt[cnt] = w;
}
bool inq[MAXN];
queue<int>q;
void spfa(LL* dis, int* col) {
    for(int i = 1; i <= n; ++i) dis[i] = inf, col[i] = 0;
    for(int i = 1; i <= k; ++i) dis[a[i]] = 0, col[a[i]] = a[i], q.push(a[i]), inq[a[i]] = 1;
    while(!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = 0;
        for(int v, i = fir[u]; i; i = nxt[i])
            if(dis[v=to[i]] > dis[u] + wt[i]) {
                dis[v] = dis[u] + wt[i];
                col[v] = col[u];
                if(!inq[v]) inq[v] = 1, q.push(v);
            }
    }
}
LL dis[2][MAXN];
int col[2][MAXN];
int U[MAXM], V[MAXM], W[MAXM];
int main () {
    int T;
    read(T);
    while(T--) {
        read(n), read(m), read(k);
        for(int i = 1; i <= n; ++i) fir[i] = 0; cnt = 0;
        for(int i = 1; i <= m; ++i)
            read(U[i]), read(V[i]), read(W[i]), link(U[i], V[i], W[i]);
        for(int i = 1; i <= k; ++i) read(a[i]);
        spfa(dis[0], col[0]);
        for(int i = 1; i <= n; ++i) fir[i] = 0; cnt = 0;
        for(int i = 1; i <= m; ++i)
            link(V[i], U[i], W[i]);
        spfa(dis[1], col[1]);
        LL ans = inf;
        for(int i = 1; i <= m; ++i) {
            int x = U[i], y = V[i];
            if(col[0][x] && col[1][y] && col[0][x]!=col[1][y])
                ans = min(ans, dis[0][x] + dis[1][y] + W[i]);
        }
        printf("%lld\n", ans);
    }
}

[GXOI/GZOI2019]旅行者 （最短路）

原文：https://www.cnblogs.com/Orz-IE/p/12051382.html