首先通过一次floyd跑出最短路，然后对每个点单独判断即可。
当然，这里出题人为了练习Dijkstra，没有写floyd的版本，但是时间复杂度是一样的。

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 105;
const int MAXM = 100000;

int u[MAXM], v[MAXM];


struct Edge {
    int from, to, dist;
    Edge(int u, int v, int d):from(u),to(v),dist(d) {}
};

struct HeapNode {   //priority_queue 的结点定义
    int d, u;
    bool operator < (const HeapNode& rhs) const {   //重载小于号是右边为优先级高
        return d > rhs.d;   //降序  那么优先级高的右边值最小
    }
};

struct Dijkstra {
    int n, m;
    vector<Edge> edges;    //保存已知的边
    vector<int> G[MAXN];    //从点出发的周围的边的编号
    bool done[MAXN]; //是否已永久标号
    int d[MAXN][MAXN]; //s到各个点的距离 d[i][j]:i-->j

    void init(int n) {
        this->n = n;
        for(int i = 1; i <= n; i++) G[i].clear();
        edges.clear();
    }
    void AddEdge(int from, int to) {
        edges.push_back(Edge(from, to, 1));
        m = edges.size();
        G[from].push_back(m-1); //保存边的编号 到 G[from]
    }
    void dijkstra(int s) {
        priority_queue<HeapNode> Q;
        for(int i = 1; i <= n; i++) d[s][i] = INF;
        d[s][s] = 0;
        memset(done, 0, sizeof(done));
        Q.push((HeapNode) {
            0, s
        });
        while(!Q.empty()) {
            HeapNode x = Q.top();   //取得最小权值（s到这个点的距离）的结点
            Q.pop();    //记得及时扔掉
            int u = x.u; //得到结点
            if(done[u]) continue;   //结点曾经被取出来过,扔掉,防止结点的重复扩展
            done[u] = true; //给结点u作更新过标记
            for(int i = 0; i < G[u].size(); i++) {  //枚举所有从结点u出发的周围的边
                Edge& e = edges[G[u][i]];   //通过边的编号在边集中查出边
                if(!done[e.to] && d[s][e.to] > d[s][u] + e.dist) {//结点e.to没更新过 并且 s到点e.to的距离 > s到点u的距离+边e的长度
                    d[s][e.to] = d[s][u] + e.dist; //松弛操作 （感觉却是拉紧）
                    Q.push((HeapNode) {
                        d[s][e.to], e.to
                    });
//                  cnt[e.to ]++;
                }
            }
        }
    }
} g;

int cnt[MAXN][MAXN];
int main() {
    int n, m, p,qd,zd;
    //freopen("最短路上的统计.in", "r", stdin);
    scanf("%d%d", &n, &m);
    g.init(n);
    for(int e = 1; e <= m; e++) {// 枚举所有边
        scanf("%d%d", &u[e], &v[e]);    //边e的两个结点u[e]和v[e]
        g.AddEdge(u[e], v[e]);
        g.AddEdge(v[e], u[e]);      //对无向图 要多一条反向路径
    }
    for(int i=1; i<=n; i++)
        g.dijkstra(i);
    for(int i=1; i<=n; i++)
        for(int j = 1; j <= n; j++) {
            for(int k = 1; k <= n; k++)
                if(i!=j&&i!=k&&j!=k) {
                    if(g.d[i][j]==g.d[i][k]+g.d[k][j])
                //  printf("%d  %d  %d  ")
                    cnt[i][j]++;
                }
        }
    scanf("%d",&p);
    while(p--) {
        scanf("%d%d",&qd,&zd);
        printf("%d\n",cnt[qd][zd]+2);
    }
    return 0;
}