题目链接:http://acm.scu.edu.cn/soj/problem.action?id=4526
Time Limit:1000ms Memory Limit:32768K

Description

给定一个n个节点，m条有向边的图，再给你起点和终点，请问其中有多少条互不重叠的从起点到终点的最短路，即互相没有公共边的最短路个数（可以有公共点），用过边的不能再用。

Input

输入第一行有一个T，表示样例个数。(T≤60)
每个样例第一行有两个整数n,m(n≤1000,m≤100000)
然后是m行，代表每一条边的起点终点和权值。 
然后是一个两个整数，代表起点和终点。

Output

输出最短路个数。

Sample Input

4
4 4
1 2 1
1 3 1
2 4 1
3 4 1
1 4
7 8
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
4 6 1
5 7 1
6 7 1
1 7
6 7
1 2 1
2 3 1
1 3 3
3 4 1
3 5 1
4 6 1
5 6 1
1 6
2 2
1 2 1
1 2 2
1 2

Sample Output

2
2
1
1

Problem solving:

最短路问题，使用邻接表的方法存边，再跑一遍Dijkstra算法(优先队列)，最后搜索一下，把能到达终点的边找出来，只要用过的就不能用了。这里我没用STL里面的优先队列，我用的是数组型的队列，方便每次都让最短的边出队。

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1010
using namespace std;
struct edgg {
    int t, s;
}Q[N * N];
struct edge {
    int u, v, w;
}e[100 * N];
struct edga {
    int node[N], path[N], w[N], num;
}pre[N];
int cnt, f[N], vis[N], dis[N], vish[100 * N];
void Add(int u, int v, int w) {
    e[++cnt] = (edge){f[u], v, w};
    f[u] = cnt;
}
void Q_sort(struct edgg a[], int n, int min) {
    int j = n - 1;
    for (int i = 0; i < n; i++)
        if (a[i].s < min)
            j = i, min = a[i].s;
    swap(a[0], a[j]);
}
void Dijkstra(int s) {
    int t, v;
    int head, tail;
    memset(vis, 0, sizeof(vis));
    memset(pre, 0, sizeof(pre));
    memset(dis, 0x3f, sizeof(dis));
    head = tail = dis[s] = 0;
    Q[tail].t = s;
    Q[tail++].s = 0;
    while (head < tail) {
        struct edgg t = Q[head++];
        if (vis[t.t])
            continue;
        vis[t.t] = 1;
        for (int i = f[t.t]; i; i = e[i].u) {
            v = e[i].v;
            if (dis[v] > t.s + e[i].w) {
                dis[v] = t.s + e[i].w;
                pre[v].num = 0;
                pre[v].path[pre[v].num] = i;
                pre[v].node[pre[v].num++] = t.t;
                Q[tail].t = v;
                Q[tail++].s = dis[v];
                Q_sort(Q + head, tail - head, dis[v]);
            }
            else if (dis[v] == t.s + e[i].w) {
                pre[v].path[pre[v].num] = i;
                pre[v].node[pre[v].num++] = t.t;
            }
        }
    }
}
void dfs(int v) {
    int t;
    for (int i = 0; i < pre[v].num; i++) {
        t = pre[v].path[i];
        if (vish[t])
            continue;
        vish[t] = 1;
        dfs(pre[v].node[i]);
    }
}
int main() {
    int s, t, u, v, w, n, m, ans, test;
    scanf("%d", &test);
    while (test--) {
        cnt = ans = 0;
        scanf("%d%d", &n, &m);
        memset(f, 0, sizeof(f));
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            Add(u, v, w);
        }
        scanf("%d%d", &s, &t);
        memset(vish, 0, sizeof(vish));
        Dijkstra(s);
        dfs(t);
        for (int i = f[s]; i; i = e[i].u)
            if (vish[i])
                ans++;
        printf("%d\n", ans);
    }
    return 0;
}