@[泰勒斯威夫特](/space/show?uid=108191) 入度为0，哪来的点走到它呀！~~(虽然我没看题)~~
by jerry3128 @ 2019-10-28 21:27:59
@[泰勒斯威夫特](/space/show?uid=108191) 一个节点入度为零不就是说明了不能再有路径到达他从而更新到他的最短路了嘛qwq
by 兮水XiShui丶 @ 2019-10-28 21:30:58
@[jerry3128](/space/show?uid=27338) 这个"入度"指的是这个点还没有爆炸的保护器的数量,是我没有说清楚.
这道题的题意是:有一张有向图,其中某些点能被走到,当且仅当它的"保护节点"全部已经被走到.求从 1 走到 n 的最短路.
by 泰勒斯威夫特 @ 2019-10-28 21:31:09
@[Kirito_Rivaille](/space/show?uid=54047) 这个"入度"指的是这个点还没有爆炸的保护节点的数量,是我没有说清楚.
这道题的题意是:有一张有向图,其中某些点能被走到,当且仅当它的所有"保护节点"全部已经被走到.给定每个节点的"保护节点",求从 1 走到 n 的最短路.
by 泰勒斯威夫特 @ 2019-10-28 21:32:26
如果某点u入度为0的时候里面的值还是0x3f3f3f3f（初始化时候的最大值没被更改），那么从原点出发一定没有一条路径走到这个点u
by 王奕霏 @ 2019-10-28 21:33:22
~~108紫题AC的“萌新”QAQ~~
by 王奕霏 @ 2019-10-28 21:34:35
@[王奕霏](/space/show?uid=42479) 为啥啊?(~~我太菜了~~)
by 泰勒斯威夫特 @ 2019-10-28 21:35:31
能走到这个点的点都已经走完了，但这个点还没被更新——没被更新就说明没找到一条路径走到这个点——而走向这个点的路径都走完了，还没找到一条从原点出发的路径走到这个点，就说明原点一定走不到这个点呀～
~~（竟敢在紫题讨论里自称萌新QAQ）~~
by 王奕霏 @ 2019-10-28 21:40:09
@[王奕霏](/space/show?uid=42479) 我的这个"入度"指的是这个点还没有爆炸的保护节点的数量,是我没有说清楚.
这道题的题意是:有一张有向图,其中某些点能被走到,当且仅当它的所有"保护节点"全部已经被走到.给定每个节点的"保护节点",求从 1 走到 n 的最短路.
我的问题是,为什么当一个点的"保护节点"全部爆炸,就可以将该节点入队呢?万一此时这个节点的最短路还没有更新怎么办啊qwq.
by 泰勒斯威夫特 @ 2019-10-28 21:43:49
就比如这样,我们从1开始跑Dij,第一步就到了3,删掉了橙边,然后3的保护节点就爆完了,我们就要把3入队了,但是这个时候3的最短路还没更新啊qwq
by 泰勒斯威夫特 @ 2019-10-28 21:49:30