首页 > 牛妹游历城市

Kur1su

发表于 2020-08-15 14:39:50

Description 牛妹现在正在1号点（自己家里），他决定前往n号点（牛妹想去的地方），中途可以多次经过1~n号点。现在，已知每个点都有个权值，如果 & ≠0，则i号点和j号点之间连有一条双向边，权值为。他想要最小化自己的行走距离，但是他计算不出来qaq。相信全牛客最聪明的你一定会吧展开全文

NaruseShiroha

发表于 2020-08-14 22:00:56

E-牛妹游历城市题面链接大致题意给出个节点的权值，如果两个点的权值的结果不为则认为这两个点之间有边相连，且边权为求问从走到点，最短路径为多少分析首先不能暴力因为点数有个，所有可能的边的数量为考虑位运算优化我们准备出 32 个组，对于每一个值，如果这个值展开全文

sunsetcolors

发表于 2020-08-15 14:41:54

E 牛妹游历城市题目地址： https://ac.nowcoder.com/acm/contest/6885/E 基本思路：比较容易让人想到最短路,但是如果直接建图跑,很明显会超时,所以我们考虑重新建图,我们将每一个二进制位设置为个虚点，将所有这一二进制位为的数都连向这个虚点,并且将入边展开全文

zqy1018_

发表于 2020-08-14 22:26:17

E 题目大意给定个点，第个点有权值。如果对于有不为，那么间有无向边，边权为。问从到的最短路。题解想了一个很憨的做法：依次考虑每一个位，对当前位建立一个新点，设为。遍历所有点，如果点满足这一位上为，那么连一条从到的边，边权为这一位对应的二进制数；展开全文

一个顶

发表于 2020-08-15 14:53:44

思路首先暴力建图肯定不行的，直接被卡死。那么想如何优化。首先我们可以按位操作，把32位看成点，然后对每个点拆点。即：对于第位(二进制) 有两个点，（入点）和（出点），向连一个边，边权为。然后对于输入的，如果当前在第位（二进制）是，那么这个点向连一条边权为的边，展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛