louisfghbvc的部落格

思路:

這題沒有演算法，不是圖論，別被騙了，從酋長起點開始走，看酋長那點到其他人的最短距離是誰，選擇那點。

再來加入那點，更新酋長那點到其他人的最短距離。記得走過的點要標記走過，避免重複走到同樣的點。依序印出走到的點即為答案。 不過一直AC不了，不知有沒有大神願意幫我看看QAQ。看不出來觀念錯在哪...。不過ITSA本身平台judge就很怪，之前就很雷，judge輸入輸出一堆問題，現在解不出來怪judge就對了啦。

#更: 這題同 [C_GD05-易] 征服部落 ，所以我解法是正確的

ERR代碼:

#include <iostream>
#include <cstring>
#define MX 10000
using namespace std;
int dis[1000][1000], min_dis[1000];
bool vis[1000];
int main()
{
    int t, n, k;

    cin >> t;
    while(t--){
        memset(vis, 0, sizeof vis);
        cin >> n >> k;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                cin >> dis[i][j];
        for(int i = 0; i < n; ++i)
            min_dis[i] = MX;
        for(int i = 0; i < n; ++i){
            if(i != 0)
                cout << " ";
            cout << k;
            vis[k] = true;
            int mn = MX, pos = k;
            for(int j = 0; j < n; ++j){
                min_dis[j] = min(min_dis[j], dis[k][j]);
                if(!vis[j] && mn > min_dis[j]){
                    mn = min_dis[j];
                    pos = j;
                }
            }
            k = pos;
        }
        cout << "\n";
    }
    return 0;
}
/*
2
6 0
0 10 10000 30 45 10000
10 0 50 10000 40 25
10000 50 0 10000 35 15
30 10000 10000 0 10000 20
45 40 35 10000 0 55
10000 25 15 20 55 0
6 0
0 10 10000 30 45 10000
10 0 5 10000 14 25
10000 5 0 10000 35 15
30 10000 10000 0 10000 2
45 14 35 10000 0 55
10000 25 15 2 55 0
*/