TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P4109
  • 题目
  • P4109写错的程序
    限制 : 时间限制 : 10000 MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

    nodgd遇到了一道最短路问题:

    输入一个 \(n\) 个节点 \(m\) 条边的有向图,求节点 $1$ 到每个节点的最短路。

    nodgd觉得这是一道水题,就写了著名的Dijkstra算法:初始化每个节点的距离为正无穷,起点(节点1)的距离为0;每次选一个没选过的dis最小的节点(如果有并列就选择编号最小的节点),将这个节点标记,然后用它的距离起更新其他未标记节点的距离。

    可惜,nodgd的程序 WA(0) 了,于是nodgd想知道,这份程序算错了多少个节点的距离。

    输入格式

    第一行两个整数 \(n,m\) ,表示节点和有向边的数量。

    接下来 \(m\) 行,每行三个整数 \(a, b, c\) ,表示一条从 \(a\)\(b\) 的边,长度为 \(c\)

    输出格式

    输出一个整数,表示nodgd算错距离的节点数量。

    样例输入

    5 6
    1 2 1
    1 3 2
    3 4 -10
    2 5 -1
    4 2 3
    4 5 8

    样例输出

    2

    提示

    样例说明
    节点 $2,5$ 的距离会算错。

    数据范围
    对于20%的数据, \(c\geq 0\)
    对于50%的数据, \(n\leq 100, m\leq 500\)
    对于100%的数据,\(n\leq 1000\)\(m\leq 5000\)

    边权绝对值不超过 $10000$ ,保证节点 $1$ 能到达所有节点,保证没有负权回路。
    两个节点之间可能有很多条边,没有边的 \(a,b\) 相等。