D. 金坷垃运输网络优化

    传统题 1000ms 256MiB

金坷垃运输网络优化

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述: 金坷垃集团要在非洲建立n个肥料仓库(编号1到n)和m条运输通道。每条通道需要消耗一定的金坷垃能量w(单位:袋)。由于非洲农业不发达,我们必须合理规划运输路线。请计算从总部(1号仓库)到其他所有仓库的最短消耗路径,并考虑以下特殊情况:

  1. 经过美国圣地亚哥的通道(编号为42的通道)消耗减半
  2. 日本专家维护的通道(编号为114的通道)消耗增加50%
  3. 非洲本地通道(编号为514的通道)有20%概率完全堵塞

输入格式

  • 第一行两个整数n, m (1 ≤ n ≤ 100, 0 ≤ m ≤ 1000)
  • 接下来m行,每行四个整数u, v, w, id,表示u和v之间有一条消耗w袋金坷垃的通道,通道编号为id

输出格式

  • 一行n个整数,表示1号仓库到每个仓库的最短能量消耗
  • 如果不可达,输出"非洲农业不发达!"

示例

输入:
3 3
1 2 10 1
2 3 6 42
1 3 20 514

输出:
0 10 13

61抱团整活赛

未参加
状态
已结束
规则
IOI(严格)
题目
7
开始于
2025-6-1 14:30
结束于
2025-6-1 16:00
持续时间
1.5 小时
主持人
参赛人数
4