题目描述(ID:12330)
标题: 最短路
标签:
详情:
给出一张N个点的无向图,问从1到N最多有可以画出多少条互不相交的路径,使得这些路径都是1到N的最短路。
在本题中,路径不相交的定义是:两条路径没有使用同一条边。
输入格式:
第一行包括两个整数n,m,代表点的个数和边的个数。
接下来m行,每行包括三个整数a,b,v,代表从a到b有一条距离为v的无向边。
输出格式:
输出一个数字,代表最多的互不相交的最短路的条数。
限制: 对于40%的数据,n,m<=10。
对于80%的数据,n,m<=100。
对于100%的数据,n,m<=1000,0<=v<=100
样例:

输入

3 3
1 2 1
1 3 1
2 3 1

输出

1
登录并解答