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

然后给出来一个点 i,问是否能找到两个点 j,k,满足:
-
k 是被特殊标记的结点;
-
用 path(x,y) 表示结点 x 到结点 y 的最短路径长度,那么 path(j,i)+path(i,k)=path(j,k)。(也可以说 j 到 k 的最短路径经过 i)
-
j=k。
这道题目如果是上图的情况,给出来的 i=5 时,可以找到 j=1,k=4 等解。但是 i=2 时,找不到符合要求的 j,k。
这道题有什么比较时间复杂度优秀的做法吗?