Luogu . 传送门 https://www.luogu.org/problemnew/show/P4366
Orz THU 众大佬, lct(注意不是 link-cut-tree, 是一个大佬)
这道题很容易让人联想到 最短路, 但是最短路需要先 建图;
暴力建出所有边的算法显然是不可行的, 因为这样会建出 \(O(n^2 + m)\) 条边;
那么我们要考虑能不能 减少一些边 , 使边的数量可以接受.
从哪里入手减少边的数量呢? 异或或许是一个不错的切入口.
举个栗子:
假设我们要从 \(001_2\) 到 \(010_2\), 我们要花费 \(2^0 + 2^1\) 的费用;
但是, 最短路有一个 优越的性质, 我们可以把边拆开来, 可以先从 \(001_2\) 到 \(000_2\), 再从 \(000_2\) 到 \(010_2\), 费用是一样的.
这样我们对于每个点 \(i\), 只需要建 \(i\) 到 \(i \ XOR \ 2^k\) 的边, 之后 Dijkstra 就可以了哈.
需要注意的是 边界情况: 从 \(i\) 到 \(j\) 经过的中间点可能超过 \(n\), 对此有 2 种处理方法:
建边和 Dijkstra 的范围调整为 \([0,n]\)
建边和 Dijkstra 的范围调整为 \([1, 2^k-1],k = min \{ k \ | \ n \leq 2^k -1 \}\)
方法 1 的代码
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<cmath>
- #include<algorithm>
- #include<queue>
- using namespace std;
- ?
- const int maxn = 100007;
- const int maxm = 2500007;
- int n, m, c;
- int edgenum, head[maxn], nxt[maxm], vet[maxm], val[maxm];
- inline void addedge(int u, int v, int w){
- ????++edgenum;
- ????vet[edgenum] = v;
- ????val[edgenum] = w;
- ????nxt[edgenum] = head[u];
- ????head[u] = edgenum;
- }
- ?
- inline int read(){
- ????int f = 1, val = 0; char ch = getchar();
- ????while ((ch <'0' || ch> '9') && (ch != '-')) ch = getchar();
- ????if (ch == '-') f = -1, ch = getchar();
- ????while (ch>= '0' && ch <= '9') val = (val <<3) + (val << 1) + ch - '0', ch = getchar();
- ????return val * f;
- }
- ?
- int dist[maxn];
- bool vis[maxn];
- #define pii pair<int, int>
- priority_queue<pii, vector< pii>, greater<pii>> Qmin;
- const int INF = 1000000007;
- inline void Dijkstra(int s){
- ????for (int i = 0; i <= n; ++i){
- ????????vis[i] = false;
- ????????dist[i] = INF;
- ????
- }
- ????dist[s] = 0; Qmin.push( make_pair(0, s) );
- ????for (int i = 0; i <= n; ++i){
- ????????while (!Qmin.empty() && vis[Qmin.top().second]) Qmin.pop();
- ????????if (Qmin.empty()) break;
- ????????int u = Qmin.top().second; Qmin.pop();
- ????????vis[u] = true;
- ????????for (int e = head[u]; e; e = nxt[e]){
- ????????????int v = vet[e], cost = val[e];
- ????????????if (dist[v]> dist[u] + cost){
- ????????????????dist[v] = dist[u] + cost;
- ????????????????Qmin.push( make_pair(dist[v], v) );
- ????????????
- }
- ????????
- }
- ????
- }
- }
- ?
- int main(){
- ????n = read(); m = read(); c = read();
- ????for (int i = 1; i <= m; ++i){
- ????????int u = read(), v = read(), w = read();
- ????????addedge(u, v, w);
- ????
- }
- ?????
- ????for (int i = 0; i <= n; ++i){
- ????????for (int j = 0; j <20; ++j){
- ????????????int to = i ^ (1 << j);
- ????????????if (to <= n) addedge(i, to, c * (1 << j));
- ????????
- }
- ????
- }
- ?????
- ????int A = read(), B = read();
- ????Dijkstra(A);
- ?????
- ????printf("%d\n", dist[B]);
- ????return 0;
- }
方法 2 的代码
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<cmath>
- #include<algorithm>
- #include<queue>
- #define pii pair<int,int>
- using namespace std;
- const int maxn = 200007;
- const int maxm = 3000007;
- int n, m, C, lgn, A, B;
- int edgenum, hea[maxn], vet[maxm], nxt[maxm], val[maxm];
- inline void addedge(int u, int v, int cost){
- ++edgenum;
- vet[edgenum] = v;
- val[edgenum] = cost;
- nxt[edgenum] = hea[u];
- hea[u] = edgenum;
- //printf("%d -> %d (%d)\n", u, v, cost);
- }
- inline int read(){
- int f=1, val=0; char ch=getchar();
- while ((ch<'0'||ch>'9')&&(ch!='-')) ch=getchar();
- if (ch=='-') f=-1,ch=getchar();
- while (ch>='0'&&ch<='9') val=(val<<3)+(val<<1)+ch-'0',ch=getchar();
- return val*f;
- }
- int dist[maxn];
- bool vis[maxn];
- priority_queue<pii, vector<pii>, greater<pii>> Qmin;
- inline void Dijkstra(int s){
- for (int i = 1; i <= n; ++i){
- vis[i] = false;
- dist[i] = 1000000000;
- }
- dist[s] = 0; Qmin.push(make_pair(0, s));
- for (int i = 1; i <= n; ++i){
- while (!Qmin.empty() && vis[Qmin.top().second]) Qmin.pop();
- if (Qmin.empty()) break;
- int u = Qmin.top().second; Qmin.pop();
- vis[u] = true;
- for (int e = hea[u]; e; e = nxt[e]){
- int v = vet[e], cost = val[e];
- if (dist[v]> dist[u] + cost) dist[v] = dist[u] + cost, Qmin.push(make_pair(dist[v], v));
- }
- }
- }
- int main(){
- n = read(); m = read(); C = read();
- for (int i = 1; i <= m; ++i){
- int u = read(), v = read(), cost = read();
- addedge(u, v, cost);
- }
- lgn = floor(log2(n)) + 1;
- n = (1 << lgn) - 1;
- for (int i = 1; i <= n; ++i){
- for (int j = 0; j < lgn; ++j)
- addedge(i, i ^ (1 << j), (1 << j) * C);
- }
- A = read(); B = read();
- Dijkstra(A);
- printf("%d\n", dist[B]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2782130.html