我认为这个题有两种情况！设一扩展节点集合叫A, 未扩展为~A1.在选择最小权值的边时　可能碰到两个（或者两个以上）结点属于~A　且到A中任意节点的最短距离都=d　相等　因此在加这个结点时　选择加入不同的节点会得到不同的生成树 2.计算一个不在Ａ中的结点v与Ａ中任意节点的最短距离的时候　发现与两个节点的最短距离相等　于是随机选择了一个(程序里可能是id值偏后的)　这样在这个节点加入到Ａ中去的时候　就有两个节点到v的距离（且是最短距离）相等　这时同样会导致生成树不唯一　请问我的理解是否正确？

• Re:做做试试就知道了，这题不难…… (250) byron 2006-11-12 17:46:14
• 我试过了 2种情况都判断AC 只判断第二种情况AC 只判断第一种情况WA 其实我在想数据是不是有疏漏 我提供两组数据 请大牛们看看 分别对应情况2 和情况1 我认为都是not unique! (71) alpc12 2006-11-12 17:58:51
  • Re:内详 (38) byron 2006-11-12 18:10:58
    • 恩 您说的这个判断我也采用的 正好对应我说的情况2 但是情形1难道不需要判断？ (0) alpc12 2006-11-12 18:14:24
      • 而且显然 只用这个判断对第二组数据的不出not unique的结论 (0) alpc12 2006-11-12 18:15:33
      • Re:这样就会把情况一也剔除了呀，相同就先加入，转换成情况二判断就行了呀^_^ (0) byron 2006-11-12 18:16:10
        • 这样么？你看看下面这组数据 及其合并情形 (155) alpc12 2006-11-12 18:24:20
        • Re:果然判断不出来，晕，但是真是水过去的…… (0) byron 2006-11-12 18:24:52
          • Re:只能说这题数据太弱了，我真是混过去了，唉…… (0) byron 2006-11-12 18:26:13
            • 呵呵 byron大牛RP真好 什么时候我又这个人品就好咯。。 混也能混过去。。 (0) alpc12 2006-11-12 18:33:07
              • Re:我不是大牛，混过去是绝对不好的……太谢谢你啦，要不又有一个知识漏洞了 (0) byron 2006-11-12 18:36:14
              • 我觉得自己写错了但是AC了，这题目数据弱弱的 (0) alpc62 2007-10-10 22:14:37