TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6368
  • 题目
  • P6368[理科综合]物理
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,512MB
    问题描述

    物理课上,nodgd一拍脑袋,发明了一个最短路算法:给无向图的每个节点制作一个小球,每条边制作一根绳子,绳子的长度就是边的权值;将最短路问题的起点对应的小球缓缓提起,然后测量每个小球到起点小球的距离,就得到了起点到每个节点的最短路。nodgd发现这个算法非常厉害——它的时间复杂度为$O(1)$。

    nodgd打算在课上给大家演示这个最短路算法,于是用数据生成器生成了一组数据,即一个$n$个节点$m$条边的无向图。nodgd发现,分别选取不同的最短路起点,有些绳子总是处于松弛状态,有些绳子总是处于绷紧状态,剩下的绳子时而绷紧时而松弛,这样可以将绳子分成三类。现在nodgd想知道,每种绳子属于哪一类?

    输入格式

    1第一行两个整数$n,m$,表示无向图的节点数和边数。

    接下来$m$行,每行三个整数$a_i,b_i,c_i$,表示第$i$条无向边连接$a_i,b_i$节点,权值为$c_i$。保证没有重边和自环。

    输出格式

    输出$m$行,第$i$行输出一个整数$k_i$,$k_i=1,2,3$分别表示第$i$根绳子总是总是松弛、总是绷紧、时而绷紧时而松弛。

    样例输入

    4 6
    1 2 1
    1 3 1
    1 4 1
    2 3 2
    2 4 2
    3 4 4

    样例输出

    2
    2
    2
    3
    3
    1

    提示

    样例说明

    • 以节点$1$作为起点时,第$1,2,3$条边的绳子绷紧;
    • 以节点$2$作为起点时,第$1,2,3,4,5$条边的绳子绷紧;
    • 以节点$3$作为起点时,第$1,2,3,4$条边的绳子绷紧;
    • 以节点$4$作为起点时,第$1,2,3,5$条边的绳子绷紧;

    数据规模与约定

    对于20%的数据,\(n\leq 10\);

    对于50%的数据,\(n\leq 100\);

    对于100%的数据,$1\leq n\leq500,\quad 0\leq m\leq n(n-1)/2,\quad 1\leq a_i,b_i\leq n,\quad 1\leq c_i\leq 10^6$。


    来源  感谢nodgd