题意

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

题解

考试时没怎么想写了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);
}
}