P1342 请柬

    • 1.3K通过
    • 4.1K提交
  • 题目提供者 yeszy 管理员
  • 评测方式 云端评测
  • 标签 图论 最短路 福建省历届夏令营 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    在电视时代,没有多少人观看戏剧表演。Malidinesia古董喜剧演员意识到这一事实,他们想宣传剧院,尤其是古色古香的喜剧片。他们已经打印请帖和所有必要的信息和计划。许多学生被雇来分发这些请柬。每个学生志愿者被指定一个确切的公共汽车站,他或她将留在那里一整天,邀请人们参与。

    这里的公交系统是非常特殊的:所有的线路都是单向的,连接两个站点。公共汽车离开起始点,到达目的地之后又空车返回起始点。学生每天早上从总部出发,乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候,所有的学生都回到总部。现在需要知道的是,学生所需的公交费用的总和最小是多少。

    输入输出格式

    输入格式:

    第1行有两个整数n、m(1<=n,m<=1000000),n是站点的个数,m是线路的个数。

    然后有m行,每行描述一个线路,包括3个整数,起始点,目的地和价格。

    总部在第1个站点,价钱都是整数,且小于1000000000。

    输出格式:

    输出一行,表示最小费用。

    输入输出样例

    输入样例#1: 复制
    4 6
    1 2 10
    2 1 60
    1 3 20
    3 4 10
    2 4 5
    4 1 50
    输出样例#1: 复制
    210 

    说明

    【注意】

    此题数据规模较大,需要使用较为高效的算法,此题不设小规模数据分数。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。