首页 > 其他分享 >[Code+#4]最短路

[Code+#4]最短路

时间:2022-12-14 21:36:54浏览次数:63  
标签:+# Code xor int 短路 times reads edge data

[\(Code\)+#4]最短路

链接:https://www.luogu.com.cn/problem/P4366

题面:给定一个\(n\)个点,\(m\)条边的无向图,若任意点对\((i,j)\)之间还有一条长为\((i xor j)\times C\)的边,求\(A\)到\(B\)的最短路。

题解:\((i xor j)\times C\)这个式子看似很毒瘤,实际上我们可以把每一位拆开来看,若要从\(9\)走到\(7\):

\(((1001)_{2} xor (111)_{2})\times C\)

\(=(1000)_{2}\times C+(10)_{2}\times C+(100)_{2}\times C\)

\(=((1001)_{2}xor(1)_{2})\times C+((1)_{2}xor(11)_{2})\times C+((11)_{2}xor(111)_{2})\times C\)

上述等式的含义即为\((1001)_{2}->(111)_{2}\)等价于\((1001)_{2}->(1)_{2}->(11)_{2}->(111)_{2}\)

推广即得,任意\((i,j)\)的边,都可以被拆成若干个\((i,(i xor 2^t))\)的边的权值和,每一个点\(i\)向\((i xor 2^t)\)连边即可。

#include<iostream>
#include<queue>
using namespace std;
struct node
{
  int v,data,nxt;
};
struct reads
{
  int num,data;
  bool operator < (const reads &a)const
  {
    return data>a.data;
  }
};
reads tmp;
priority_queue<reads>q;
node edge[4000001];
int head[200001],len,dis[200001],n,m,C;
bool used[200001];
void add(int x,int y,int z)
{
  edge[++len].v=y;
  edge[len].data=z;
  edge[len].nxt=head[x];
  head[x]=len;
  return;
}
reads make_reads(int x,int y)
{
  tmp.num=x;
  tmp.data=y;
  return tmp;
}
void dijkstra(int x)
{
  q.push(make_reads(x,0));
  for (int i=0;i<=n;++i)
    dis[i]=(i!=x)*1e9;
  int top;
  while (!q.empty())
    {
      top=q.top().num;
      q.pop();
      if (used[top])
	continue;
      used[top]=1;
      for (int i=head[top];i>0;i=edge[i].nxt)
	if (dis[edge[i].v]>dis[top]+edge[i].data)
	  {
	    dis[edge[i].v]=dis[top]+edge[i].data;
	    q.push(make_reads(edge[i].v,dis[edge[i].v]));
	  }
    }
}
int main()
{
  int x,y,z,A,B;
  cin>>n>>m>>C;
  for (int i=1;i<=m;++i)
    {
      cin>>x>>y>>z;
      add(x,y,z);
    }
  for (int i=0;i<=n;++i)
    for (int k=1;k<=2*n;k*=2)
      if ((i^k)<=n)
	add(i,i^k,k*C);
  cin>>A>>B;
  dijkstra(A);
  cout<<dis[B]<<endl;
  return 0;
}

标签:+#,Code,xor,int,短路,times,reads,edge,data
From: https://www.cnblogs.com/zhouhuanyi/p/16983594.html

相关文章

  • go代码调试之vscode设置环境变量
    go代码调试之vscode设置环境变量只能通过vscode的debug的形式允许测试代码,不能通过gotest获取1.创建lauch.json文件2.然后在项目目录中会自动创建.vscode的目录3.在......
  • C++ 模板
    函数模板基础建立一个通用的函数,将函数返回值类型和形参类型不具体指定,用一个虚拟的类型来表示template<typenameT>函数的声明和定义template---声明创建模板typen......
  • [LeetCode]003-无重复字符的最长子串
    >>>传送门题目给定一个字符串s,请你找出其中不含有重复字符的最长子串的长度。示例示例1输入:s="abcabcbb"输出:3解释:因为无重复字符的最长子串是"abc",......
  • [Code+#4]最短路
    [$Code$+#4]最短路链接:https://www.luogu.com.cn/problem/P4366题面:给定一个$n$个点,$m$条边的无向图,若任意点对$(i,j)$之间还有一条长为$(ixorj)\timesC$的边,求$A......
  • 浅析次短路
    统计次短路数量Sightseeing求最短路与次短路(只与最短路长度相差\(1\)的次短路)数量之和。最短路首先回顾我们如何统计最短路数量,我们使用\(cnt[j]\)表示从源点到\(......
  • web前端--Code Review
    2022年马上结束了,年底了,做一些总结吧。主要关于每次前端的CodeReview注意事项,做的一些总结如下:数据处理在提交前处理,尽量不要在onChange中处理列表与详情页的源进源......
  • PHPstorm配置PHP_CodeSniffer代码检查工具
    目录1.PHPCodeSniffer介绍2.安装PHP_CodeSniffer3.使用PHPStorm设置PHPCS4.测试PHP_CodeSniffer的检测功能参考资料1.PHPCodeSniffer介绍PHP_CodeSniffer对PHP文......
  • PWN ORW 最短的shellcode(33字节!)
    前言:下面的rdx就是read(1,buf,n)中的n,这个值太大或者太小都没办法正常读。所以分两种大情况:orw:(64bit,34字节,针对需要调整rdx的情况:)shellcode=asm('''movedx,0x6761......
  • AtCoder Regular Contest 143 E Reversi
    AtCoder传送门洛谷传送门翻转一个点会把它相邻的点全部翻转,因此先从叶子开始自下而上考虑。不难发现,如果这个叶子是白色,那么它一定比它的父亲先翻转(否则它就翻不了了);而......
  • AtCoder Regular Contest 150 F Constant Sum Subsequence
    AtCoder传送门洛谷传送门定义\(\mathrm{nxt}(i,x)\)为最小的\(j\)满足\(a_j=x\)且\(j>i\),\(\mathrm{pre}(i,x)\)为最大的\(j\)满足\(a_j=x\)且\(j<......