洛谷题解：P15804 [GESP202603 八级] 消息查找

张开发
• 2026/4/21 4:06:01 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

洛谷题解：P15804 [GESP202603 八级] 消息查找
考场上的代码赛后发现改五十个字符就过了呜呜呜。题意给一个图每个节点指向上一个节点有最多1000 10001000条附加边从一个大编号的点指向小编号快速求任意两点的距离。思路由于指向上一个节点的边太浪费时间所以可以记录一些关键点即{ i ∣ a i 0 ∨ a j i } \{i|a_i0\lor a_ji\}{i∣ai​0∨aj​i}然后计算两两之间的距离询问的时候查找两个点最近的关键点把距离加起来输出。代码#includebits/stdc.husingnamespacestd;intn,q,a[100001],id[100001],l[100001],r[100001],d[2001][2001],vis[100001];vectorinthv;intmain(){//读入cinnq;hv.push_back(0);//占位for(inti1;in;i){cina[i];if(a[i])vis[i]vis[a[i]]1;//记录关键点}for(inti1;in;i)if(vis[i])hv.push_back(i),id[i]hv.size()-1;//映射//计算距离最近的关键点编号for(inti1,la0;in;l[i]la,i)if(id[i])lai;for(intin,lan1;i;r[i]la,i--)if(id[i])lai;//求最短路for(inti1;ihv.size();i){for(intj1;ji;j)d[i][j]0x3f3f3f3f;d[i][i]0;for(intji;j1;j--){d[i][j-1]min(d[i][j-1],d[i][j]hv[j]-hv[j-1]);//直接到达if(a[hv[j]])d[i][id[a[hv[j]]]]min(d[i][id[a[hv[j]]]],d[i][j]1);//跳跃到达}}while(q--){intx,y;cinxy;if(l[x]r[y])coutx-y\n;//如果中间没有关键点elsecoutx-l[x]d[id[l[x]]][id[r[y]]]r[y]-y\n;//输出距离之和}return0;//完结散花}原文链接

更多文章