#577. NOIP2012TG-16

NOIP2012TG-16

  1. (不定项选择题,正确答案数 ≥ 1)已知带权有向图 GG 上的所有权值均为正整数,记顶点 uu 到顶点 vv 的最短路径的权值为 d(u,v)d(u,v)。若 v1v2v3v4v5v_1,v_2,v_3,v_4,v_5 是图 G 上的顶点,且它们之间两两都存路径可达,则以下说法正确的有( )。

{{ multiselect(1) }}

  • v1v_1v2v_2 的最短路径可能包含一个环
  • d(v1,v2)=d(v2,v1)d(v_1,v_2)=d(v_2,v_1)
  • d(v1,v3)d(v1,v2)+d(v2,v3)d(v_1,v_3)≤d(v_1,v_2)+d(v_2,v_3)
  • 如果 v1v2v3v4v5v_1 → v_2 → v_3 → v_4 → v_5v1v_1v5v_5 的一条最短路径,那么 v2v3v4v_2 → v_3 → v_4v2v_2v4v_4 的一条最短路径