[プログラマー]level-3位(floydとshallアルゴリズム)

順位をつける
プログラマーがランキングの問題に遭遇
これはフロイドとシエルアルゴリズムを用いた問題である.
フロイドとシエルが何なのかを知り、解いてみよう~!
羅東彬のアルゴリズムのビデオ

マルチアウトアルゴリズム:1つの頂点からすべての頂点への最短パス

floodとshall:すべての頂点からすべての頂点への最短パス
値は

の2次元配列(書き出しという名前の1次元配列)

に格納されると考えられる.

x->yのコストは、x->ノード1+ノード1->yの合計コストよりも低い

更新

 #include <string>
 #include <vector>

using namespace std;

int number = 4;
int INF = 100000000;

//자료 배열 초기화 ( i > j 거리)
int a[4][4] = {
    {0, 5, INF, 8},
    {7, 0, 9, INF},
    {2, INF, 0, 4},
    {INF, INF, 3, 0}
};

void floydWarchall() {
    //결과 그래프 초기화
    int d[number][number];
    
    for(int i = 0; i < number; i++) {
        for (int j = 0; j < number; j++) {
            d[i][j] = a[i][j];
        }
    }
    
    //3중포문으로 구현
    //k = 거쳐가는 노드
    for (int k = 0; k < number; k++) {
        //i는 출발노드
        for (int i = 0; i < number; i++) {
            //j는 도착노드
            for (int j = 0; j < number; j++) {
                // 갱신
                if (d[i][k] + d[k][j] < d[i][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}

プログラマーの問題に適用しましょう.
まず

1～5つのノードがあると報告されていますが、資料を並べてみましょう.

は全部で100人の選手が

人います.

勝/敗なのでブール配列

bool a[101][101];

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    for (int i = 0; i < results.size(); i++) {
        int x = result[i][0];
        int y = result[i][1];
        //x 가 y를 이김
        a[x][y] = true;
    }
    
    return answer;
}

あなたが学んだことをあなたに適用すると

for(int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[i][k] && a[k][j]) {
                    //a[i][j] = a[i][k] + a[k][j];
                    a[i][j] = true;
                }
            }
        }
    }

このような三重複文が現れる
今思い出して正解を探すロジック
aがbに勝てば,bがcに勝てば,aがcに勝つと見なすことができる.
その三重砲口を撃った後.
選手一人一人が勝つかどうかを知ることができる.
自分のn-1番の勝敗以外は影響を受けていればいい

この問題に適用する場合,最大値を算出して更新するよりも,過去への影響力が真/偽値であるか,+追加すると,1人当たりn−1の結果が得られることを理解すべきである.

勝負は重要ではなく、勝負の有無に影響力がある.

完全コード

#include <string>
#include <vector>

using namespace std;

bool a[101][101];

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    for (int i = 0; i < results.size(); i++) {
        int x = results[i][0];
        int y = results[i][1];
        //x 가 y를 이김
        a[x][y] = true;
    }
    
    for(int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[i][k] && a[k][j]) {
                    //a[i][j] = a[i][k] + a[k][j];
                    a[i][j] = true;
                }
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        int count = 0;
        for (int j = 1; j <= n; j++) {
            if (a[i][j] || a[j][i]) count++;
        }
        
        if (count == n - 1) answer++;
    }
    
    
    return answer;
}