UVa11792 - Krochanska is Here(BFS)

題目大意

中文連結，她講得太好了
題目連結

重點觀念

• 最短路徑快速演算法，與 dijkstra 相同，但使用 queue 來實作
• 目標重點：找出 \(min(重點車站到其他重點車站的平均值)\)

分析

• 由於是要找出 \(min(重點車站到其他能抵達重點車站的平均值)\)，題目說重點車站最多只有 100，因此使用暴力解
• 題目是說要找出平均，但是題目是要找到所有能抵達的重要車站，但因為每一個車站都要能夠抵達全部的重要車站，因此分母都是相同，就可以進行省略，直接計算距離即可。

參考連結

11792 - Krochanska is Here by morrir821028
UVa 11792 - Krochanska is Here
中文連結，她講得太好了

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 10020
#define INF 0x3f3f3f
using namespace std;
int t, n, m;
vector<int> edge[MAXN]; //邊的陣列
int visit[MAXN];
int dist[MAXN], important[MAXN]; //dist 從 x 到 index 的距離
//important 重要車站，當經過的路徑大於 2，就是重要車站

//不使用 dijkstra，因為每一個權重都相同，因此使用普通的 queue 就好
int spfa(int root){ //don't using dijkstra, because each have same weights
    for(int i = 1; i <= n; i++) dist[i] = INF; //root 一開始無法抵達這些點，因此都次 INF
    memset(visit, 0, sizeof(visit));

    deque<int> q; //queue 類似於 dijkstra piority queue
    q.push_back(root); 
    dist[root] = 0; //root 到本身為 0

    while(!q.empty()){
        root = q.front(); q.pop_front();
        for(auto it: edge[root]){
            if(dist[it] > dist[root] + 1){
                dist[it] = dist[root] + 1;
                if(!visit[it]){
                    visit[it] = 1;
                    q.push_back(it);
                }
            }
        }
    }

    int ans = 0; 
    for(int i = 1; i <= n; i++){ //計算可以抵達每一個車站，使用多少距離
        if(important[i] > 1) ans += dist[i]; //如果 root 沒辦法抵達此車站，那就會是 +INF
    }
    return ans;
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i = 1; i <= n; i++) edge[i].clear();

        memset(important, 0, sizeof(important));
        while(m--){
            int pre, next;
            cin >> pre;
            while(cin >> next && next){
                edge[pre].push_back(next); //有向圖
                edge[next].push_back(pre);
                important[pre]++; //經過的路徑 + 1
                pre = next;
            }
            important[pre]++;  //經過的路徑 + 1
        }

        //min_dist 當前的最小距離，ans 當前最小距離的車站
        int ans = 0, min_dist = INF, spfa_dist;
        for(int i = 1; i <= n; i++){
            if(important[i] > 1){ //當經過的路徑大於 2，就是重要車站
                //cout << "important " << i << "\n";
                spfa_dist = spfa(i);
                //cout << "spfa_dist " << spfa_dist << "\n";
                if(spfa_dist < min_dist){
                    ans = i;
                    min_dist = spfa_dist;
                }
            }
        }
        cout << "Krochanska is in: " << ans << "\n"; //輸出答案
    }
    return 0;
}