ZOJ 2760 HOW MANY SHORTEST PATH (不相交的最短路径个数)

【题意】给定一个有N（N<=100）个节点的有向图，求不相交的最短路径的个数（两条路径没有公共边）。 【思考】首先用Floyd求最短路径，将最短路径上的边加入到网络流中，保证从s->t的一个流一定是最短路径，这样也保证了网络 流动建模是正确的性。 【求最短路径上的边】满足最优子结构的性质：(i,j)是最短路径上的边当且仅当dist[s][i] + edge[i][j] + dist [j] [t] = dist[s][t]。 起初，我以为 dist[s][j] = dist[s][i] + edge[i][j] 就可以了，但这显然是错误的。 这只是满足点 i 到点 s 是最短路径，但不保证点 j 到点 t 也是最短路径，自然也不保证 (i, j) 是最短路径上的边 .

([question meaning] given a directed graph with n (n < = 100) nodes, find the number of disjoint shortest paths (two paths have no common edge). [thinking] first, use Floyd to find the shortest path and add the edge on the shortest path to the network flow to ensure that a flow from S - > t must be the shortest path, which also ensures the correctness of network flow modeling. [find the edge on the shortest path] satisfies the properties of the optimal substructure: (I, J) is the edge on the shortest path if and only if dist [S] [i] + edge [i] [J] + dist [J] [t] = dist [S] [t]. At first, I thought dist [S] [J] = dist [S] [i] + edge [i] [J], but it was obviously wrong. This only satisfies that point I to point s is the shortest path, but it does not guarantee that point J to point t is also the shortest path. Naturally, it does not guarantee that (I, J) is the edge on the shortest path
)