题目

据说是套路题= =

那我们就放三种方法~

题解

第一种是我 $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);
    }
}
分类: 文章

quhengyi11

AFO 有缘再见

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注