• [1733] 忍者的刺探任务

  • 时间限制: 1000 ms　内存限制: 65535 K
  • 问题描述

  • 日本战国时期，岛津家的忍者组织为了完成大名的任务，需要去其他大名的领地刺探情报，但是部分其他大名的辖地并不是相邻的，而且路径也不是唯一的，所以你需要帮他计算出遍历所有目标的最少路径，并且如果路途中守军武力值大于忍者，则忍者不能过这条路。

  • 输入
  • 第一行输入整数T(1 <= T <= 100),表明有T组数据。
    第二行输入整数,o,m,n(0<=o<=10,1<=m<=500,0<=n<=1000),分别表明忍者的武力值，刺探的大名城镇数量，连接大名城镇的路径数量。
    后面n行数据，输入a，b，c，d，(1 <= a,b <= m , 0 <= c <= 100, 0 <= d <= 10)表示a和b之前有路径长度为c的路，且d为路径上守军的武力值。
  • 输出
  • 如果忍者可以刺探成功，则输出“YES”，并再换行输出路径的总值
    如果忍者刺探失败，则输出“NO”
  • 样例输入
  • 2
2 3 4
1 2 3 1
1 3 2 2
2 3 1 4
2 3 2 1

1 3 3
1 2 3 1
2 1 2 2
2 3 1 2
  • 样例输出
  • YES
4
NO
  • 提示
  • 无
  • 来源
  • 2018暑期集训出题练习
  • 操作

显示春菜