【图论】口胡题,可以怎么做
  • 板块学术版
  • 楼主66xyyd
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/12/24 10:24
  • 上次更新2023/12/24 12:10:03
查看原帖
【图论】口胡题,可以怎么做
946515
66xyyd楼主2023/12/24 10:24

给出一张有向带权图 GG,其中有一些结点被打上了特殊标记。看起来可能是这个样子的(加黑的是特殊标记的结点):

一张图

然后给出来一个点 ii,问是否能找到两个点 j,kj,k,满足:

  • kk 是被特殊标记的结点;

  • 用 path⁡(x,y)\operatorname{path}(x,y) 表示结点 xx 到结点 yy 的最短路径长度,那么 path⁡(j,i)+path⁡(i,k)=path⁡(j,k)\operatorname{path}(j,i)+\operatorname{path}(i,k)=\operatorname{path}(j,k)。(也可以说 jj 到 kk 的最短路径经过 ii)

  • j≠kj \neq k。

这道题目如果是上图的情况,给出来的 i=5i=5 时,可以找到 j=1,k=4j=1,k=4 等解。但是 i=2i=2 时,找不到符合要求的 j,kj,k。

这道题有什么比较时间复杂度优秀的做法吗?

2023/12/24 10:24
加载中...