最短路图
这是一个图论的小trick。
对于一些只能在最短路上操作且可能同时存在多条最短路的问题，可以试着采用建最短路图的方法：将最短路径上的边放在一个新的图中，使得问题能够在一个DAG(有向无环图)上操作。
大致的方法是：
若我们需要 (1-n) 的最短路图，我们可以先从 (1) 开始跑一遍最短路，得到 (dis1[i]) ，然后在反图上跑一遍 (n) 最短路 (dis2[i]) 。然后枚举每条边，若边 ((u,v,w)) 满足 (dis1[u]+w+dis2[v]=dis1[n]) ，那么这条边在最短路图上。
具体实现看例题：
例题：取边方案
题目描述
给你一张有 (n) 个点 (m) 条边的无向连通图，每条边有边权，设 (disa_i) 表示这张图中点 (i) 到点 (1) 的距离。
现在要求你在这张图中删去 (m-(n-1)) 条边，使得这张图变成一棵树，设 (dib_i) 为这棵树中点 (i) 到 点 (1) 的最短距离。
现在求解有多少种删边方案，使得对于任意的 (i) ，都有 (disa_i=disb_i) 。
输入格式
第一行包含两个正整数 (n,m) ，表示无向连通图的点数和边数。
接下来有 (m) 行，每行有 (3) 个正整数 (u,v,w) ，表示点 (u) 和点 (v) 之间有一条边权为 (w) 的无向边。
数据保证无重边、无自环。
输出格式
输出一行一个整数，表示满足条件的方案数对 (2147483647) 取模的结果。
样例输入
3 3
1 2 2
1 3 1
2 3 1
样例输出
2
样例解释
删去 (1st) or (3rd) 边都能满足条件。
由定义我们可以知道，在本题中只要是最短路图的生成树，都是合法的。
所以只需要枚举生成树个数就可以了。
如何高效枚举？
枚举生成树，可以看做给每个点选一个父亲，那么每个点可选的父亲数就是这个点的入度，那么入度之积就是答案了。