据说是套路题= =
那我们就放三种方法～
题解
第一种是我 $yy$的
考虑一条合法的最短路，它的最后一条边一定指向一个关键点，那么我们可以记录每个点到最近关键点 $(u_1,dis_1)$和第二近关键点 $(u_2,dis_2)$，这里只需要保证 $u_1\ne u_2 \&\& dis_1 \leq dis_2$即可，然后我们就可以枚举指向关键点的边 $(u,v)$(即 $v$为关键点)，然后用 $u$离最近的不是 $v$的关键点的距离更新答案即可
第二种是看题解的
考虑一条边，它可能会对答案贡献的路径的一条边经过，我们算出这个边 $(u,v)$两条边分别离最近关键点的距离 $dis1[u],dis2[v]$，然后更新答案即可，注意的是我们需要记录一下离它最近的关键点是谁，如果都是一个关键点可以不更新答案，因为这条路径总会在另一个地方被更新。这种方法的好处是不用维护次近关键点，但是麻烦的是要建反图跑两个 $dis$
第三种是 $snakes$告诉我的
记住一个性质叫做不同的两个数肯定有一位的二进制位相同 (废话)
那么我们可以枚举每一位二进制，图还是原来那个图，比如说枚举到第一位的二进制，我们把点的编号为奇数的 (也就是第一位二进制为 $1$) 的关键点，从 $S$到它们连一条边，然后把点的编号为偶数的关键点从它们到 $T$连一条边，中间的图还是原来的图，然后跑一遍最短路。然后再把 $S$和 $T$倒过来跑一遍。
我们记答案路径为 $path(u,v)$，因为 $u,v$是不同的，所以必定会有一个二进制位不同，那么在上面的方法中一定会对答案造成贡献。并且因为一个点不可能即被 $S$连又被 $T$连，所以保证了起点和终点是不同的。这个方法坏处就是多一个 $log$
只打了第一种的代码 $qwq$，而且因为细节麻烦还 $WA$了几次= =
#include<bits/stdc++.h>
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define mod 1000000007
#define eps 1e-4
#define lowbit(x) (x & -x)
#define N 100005
#define ls tr[u].s[0]
#define rs tr[u].s[1]
#define cl(arr) memset(arr, 0, sizeof arr)
#define pi std::pair<ll, int>
int head[N], tot, f[N][2], k, a[N], n, m, T, cnt;
ll dis[N][2], ans;
bool fl[N];
struct edge {
int nxt, v, w;
} e[N << 3];
inline void addedge (int u, int v, int w)
{
e[++tot] = (edge) {head[u], v, w};
head[u] = tot;
}
std::map<pi, int> uni;
inline void clear ()
{
cl(head);
cl(fl);
cl(f);
uni.clear();
tot = 0; cnt = 0;
}
std::priority_queue< pi > q;
inline int check (int v, int dist)
{
return dis[v][0] > dist ? 0 : dis[v][1] > dist ? 1 : -1;
}
inline void bfs ()
{
memset(dis, 0x3f, sizeof dis);
ans = dis[0][0];
fo (i, 1, k) { fl[a[i]] = 1; dis[a[i]][0] = dis[a[i]][1] = 0; q.push(mp(0, a[i])); f[a[i]][0] = f[a[i]][1] = a[i]; }
while (!q.empty())
{
pi tmp = q.top(); q.pop();
int u = tmp.S, dist = -tmp.F, now, last;
if (dis[u][1] < dist) continue;
last = (dis[u][0] == dist) ? 0 : 1;
if (f[u][last] == 0) continue;
edge (i, u)
{
if (dis[v][0] > dist + e[i].w)
{
if (f[v][0] != f[u][last])
{
dis[v][1] = dis[v][0]; f[v][1] = f[v][0];
dis[v][0] = dist + e[i].w;
f[v][0] = f[u][last];
}
else
{
dis[v][0] = dist + e[i].w;
}
q.push(mp(-dis[v][0], v));
}
else
{
if (dis[v][1] > dist + e[i].w && f[v][0] != f[u][last])
{
dis[v][1] = dist + e[i].w;
f[v][1] = f[u][last];
q.push(mp(-dis[v][1], v));
}
}
}
}
}
ll uu[N << 3], vv[N << 3], ww[N << 3];
main ()
{
scanf("%d", &T);
while (T--)
{
clear();
scanf("%d %d %d", &n, &m, &k);
fo (i, 1, m)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
if (u == v) continue;
if (uni.find(mp(u, v)) != uni.end() && uni[mp(u, v)] < w) continue;
uni[mp(u, v)] = w;
}
for (std::map<pi, int>::iterator it = uni.begin(); it != uni.end(); ++it)
{
uu[++cnt] = it -> F.F; vv[cnt] = it -> F.S; ww[cnt] = it -> S;
addedge(uu[cnt], vv[cnt], ww[cnt]);
}
fo (i, 1, k) scanf("%d", &a[i]);
bfs();
fo (i, 1, cnt)
if (fl[vv[i]])
{
if (f[uu[i]][0] != vv[i])
ans = std::min(ans, ww[i] + dis[uu[i]][0]);
else
ans = std::min(ans, ww[i] + dis[uu[i]][1]);
}
printf("%lld\n", ans);
}
}
0 条评论