TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4109
  • Problem
  • P4109写错的程序
    Limits : Time Limit : 10000 MS   Memory Limit : 262144 KB
    Judgment Tips : 1s,256MB
    Description

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

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

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

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

    Input Format

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

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

    Output Format

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

    Sample Input

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

    Sample Output

    2

    Hint

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

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

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


    Source  nodgd坑