「Luogu P4366」[Code+#4]最短路

发表于 |
字数统计: 603 | 阅读时长 ≈ 3

给定一个$n$个点的有向图和一个常数$c$，其中对于任意的$i$和$j$，有一条边权$(i\operatorname{xor}j)\times C$的边。还给定$m$条边，第$i$条边从$u_i$到$v_i$，边权为$w_i$，求出$s$到$t$的最短路。

$\texttt{Data Range:}n\leq 10^5,m\leq 5\times 10^5,1\leq u_i,v_i\leq n,1\leq w_i\leq 100$

链接

Luogu P4366

LOJ 6354

题解

直接建图跑最短路是不行的，因为边数是$n^2m$级别的，要优化建图。

对于$x$到$y$的边，其权值为$x\operatorname{xor}y$，也即

其中，$y_i$为$y$在二进制下第$i$位的值$\times2^i$。

为什么呢？

因为对于每一次异或，只会修改一个位置上的数，对别的位置没有影响。所以说从$x$到$y$只需要这样一个一个走即可，对答案没有影响

所以只需要对任意的点$i$向$2^j$连$i\operatorname{xor}2^j$的边，再跑最短路即可，边数立马降至$n\log n+m$级别。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAXN=1e5+51,MAXM=2.2e6+51;
struct Edge{
    ll to,prev,dist;
};
struct Tuple{
    ll node,dist;
    inline bool operator <(const Tuple &rhs)const
    {
        return this->dist>rhs.dist;
    }
};
Edge ed[MAXM];
priority_queue<Tuple>pq;
ll nc,ec,tot,from,to,dist,wt,source;
ll last[MAXN],minn[MAXN],inQueue[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline void addEdge(ll from,ll to,ll dist)
{
    ed[++tot].prev=last[from];
    ed[tot].to=to;
    ed[tot].dist=dist;
    last[from]=tot;
}
inline void Dijkstra(ll source)
{
    ll top;
    memset(minn,0x3f,sizeof(minn));
    pq.push((Tuple){source,0}),minn[source]=0,inQueue[source]=1;
    while(!pq.empty())
    {
        top=pq.top().node,pq.pop();
        for(register int i=last[top];i;i=ed[i].prev)
        {
            if(minn[top]+ed[i].dist<minn[ed[i].to])
            {
                minn[ed[i].to]=minn[top]+ed[i].dist;
                pq.push((Tuple){ed[i].to,minn[ed[i].to]});
            }
        }
    }
}
int main()
{
    nc=read(),ec=read(),wt=read();
    for(register int i=0;i<ec;i++)
    {
        from=read(),to=read(),dist=read();
        addEdge(from,to,dist);
    }
    for(register int i=0;i<=nc;i++)
    {
        for(register int j=1;j<=nc;j<<=1)
        {
            if((i^j)<=nc)
            {
                addEdge(i,i^j,j*wt);
            }
        }
    }
    Dijkstra(source=read());
    printf("%d\n",minn[to=read()]);
}