louisfghbvc的部落格

題目大意:  問你全部最短路徑中，幾個路徑被攔截

思路:  看到最短路會想到甚麼，沒錯就BFS。用一個陣列存最短路徑值。以及用queue裡面放當前點，距離，是否被攔截。O(N^2). 

代碼:  

#include <bits/stdc++.h>

#define louisfghbvc int t; cin >> t; while(t--)
using namespace std;

void dbg_out() { cerr << " end.\n"; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

struct node{
    int u, d;
    bool isgg;
};

void solve(){
    int n, a, p, b;
    scanf("%d,%d,%d,%d", &n, &a, &p, &b);

    int adj[n+1][n+1];
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            cin >> adj[i][j];

    int dis[n+2];
    memset(dis, 0x3f, sizeof dis);

    double cnt = 0, gg = 0;
    queue<node> q;
    q.push({a, 0, a==b});

    while(q.size()){
        node tmp = q.front(); q.pop();
        int u = tmp.u, d = tmp.d;
        bool isgg = tmp.isgg;

        dis[u] = d;
        if(u == p){
            if(isgg) gg++;
            cnt++;
        }

        for(int v = 1; v <= n; ++v){
            if(adj[u][v]){
                if(d+1 < dis[v]) q.push({v, d+1, isgg|(v==b)});
            }
        }
    }
    printf("%0.3f\n", gg/cnt);
}

int main()
{
    //louisfghbvc{
        solve();
    //}
    return 0;
}