[白俊]13911号-家を探す(C++)

質問リンク

位置決めの目的

グラフィック問題を繰り返し解くことで,ほとんどの問題は優先キューのマルチタスクアルゴリズムを用いて解決できる.複数の専門家グループを適用すれば,異なる問題の詳細条件のみを処理すれば,問題を解決できる.
しかし、この問題は違う.Daestraアルゴリズムをよりよく理解したと言える...問題も無理に作った感じではなく、実用的で面白いです.もちろん、実際に応用したいなら、地図をモデリングするのはもっと難しいかもしれません.

知るところ

私のコードも答えを得ることができます.タイムアウトするだけ...画期的な考えはなく、for文を勝手に使って、なんとか答えを求めるだけです.模範解答から得たものを整理する.

1つ目:2つの頂点間で2つ以上の幹線を処理する

図形の幹線情報を入力する場合は、(頂点1、頂点2、重み付け)(u, v, w)などの方式で入力するのが一般的である.それを格納する方式は隣接テーブルと隣接マトリクスがあり,性能面では隣接テーブルがずっと優れているので,できるだけ隣接テーブルを用いる.しかし、これらの問題では、「2つの頂点の間に2本以上の幹線が存在する可能性があります.」このような条件は時々気分が悪くなることがあります.
常に最短距離を求めるのが問題なので、2本以上の幹線があれば重み付け値をより小さな値に格納できます.ただし、これを隣接リストとして処理する場合は、1本の幹線の情報を入力するたびに、同じ頂点に接続された幹線があるかどうかを検索します.これは面倒で、隣接するリストのパフォーマンスのメリットを相殺するのに十分なコストがかかります.
しかし、複数の幹線の中で最も重みの小さいものを選択する必要はありません.マルチアウトアルゴリズムは、すべての頂点を巡回しながら、各頂点に接続されているすべての幹線をチェックすることによって、隣接する頂点の最短距離を更新します.更新の条件は、幹線に移動したときに到達する頂点の距離が既存の入力よりも小さいことです.したがって,2本以上の幹線があっても,隣接テーブルを用いてマルチアウトプットアルゴリズムを実行することは全く問題ない.
もちろん、入力時に最も重みの小さい幹線が1本しか残っていなければ、その幹線をチェックする演算を減らすことができますが、1本の幹線だけを残す操作はより多くの演算量を必要とするので、これは愚かな考えです.
では、なぜその条件を不快に与えるのでしょうか.隣接テーブルを使用するのは問題ではありませんが、隣接マトリクスを使用すると問題が発生します.同じ頂点を接続する2つの幹線が連続して与えられると、隣接するマトリクスはウェイトを上書きし続け、最後に入力した情報のみが残ります.しかし、最後に入力した重みが最高値であることが保証されないため、問題が発生しました.普通は隣接表を使うので大丈夫ですが...一人で無駄なことをしている.後でこの条件をあげても気分が悪くならないでください.

2つ目:マルチゾーンアルゴリズムを更新する距離

問題はマクドナルドとスターバックスが一つだったらいいのですが、問題はいくつかあります.私が作ったコードは、マクドナルドとスターバックスの回転ドアをすべて確認することです.このように、マクナールとスバークは同じ場所に存在する可能性があり、最悪の場合、マルチ出口アルゴリズムを(V-1)*(V-1)回回転させるべきである.Vの範囲は10000であるため、1億回近く実行された.もちろんタイムアウトが発生します.
どうする?
多益アルゴリズムが一つの頂点から始めなければならないという固定観念を捨てればよい.マクドナルドが3冊ある家を探したいなら、どのマクドナルドでも一番近いマクドナルドから一番近い距離を知っていればいいです.だからすべてのマクドナルドノードを起点として優先順位の列に置いて、それから始めましょう.
1番の頂点が始点の場合、1番からすべての頂点までの最短距離がわかります.でも2番から3番までの最短距離だとは知りませんでしたこれを手に入れるには、2番からもう一度回ります.この場合、1番頂点を起点として求めた距離ベクトルは使用できませんが、初期化後の新しい距離ベクトルを使用します.距離ベクトルを使用し続けると、各頂点は1番と2番の最短距離でより小さな値に更新されます.
この問題の特殊な状況は,複数の始点から各頂点までの最短距離での最切り上げが必要であるため,距離ベクトルを繰り返し用いて求めることができる.距離ベクトルを繰り返して複数回のマルチアウトアルゴリズムを実行しても、優先キューに複数の開始点を配置して1回だけ実行しても、結果は同じです.逆に考えると、すべての家がぐるっと回って、マクドナルドの最短距離の最高価格をその家に使います.
マクドナルドを重み付け0に接続する開始ノードである「スタックノード」の概念も導入できます.これにより、複数の開始ノードを1つのスタックノードに結合し、複数のツリーの[頂点から](From Vertex)の概念に対応します.しかし、これも所与の頂点の外に頂点を追加するものであり、いずれにしてもノードをスタックする役割は各始点を優先キューに配置することであるため、概念的には良いが、そうする必要はない.

3つ目:配列内のデータの検索

私が作成したコードでは、isHouse()という関数を定義して、それが家かどうかを決定します.スターバックス、マクナールの頂点番号を含むベクトルを線形に検索し、その頂点が家であるかどうかの関数を見つけます.線形探索は基本的に時間複雑度O(n)であり,かなり遅い演算である.出費が大きいのは分かっていたが、ほかの方法は見つからなかった.
方法はスバークに着目し、マナールが起点だ.始点なので距離ベクトルの値は0です.この値を利用すると,線形検索を行う必要がなく,直接インデックスで知ることができる.既存の価格を利用してみます.

私が作った世界コード

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 100000000
using namespace std;

vector<pair<int, int> > map[10001];
vector<int> dist_m(10001, INF);
vector<int> dist_s(10001, INF);

class Info {
public:
    int node, cost;

    bool operator<(const Info &rhs) const {
        return this->cost > rhs.cost;
    }
};
priority_queue<Info> pq;
priority_queue<Info> res;

bool isHouse(int vertex, vector<int> &mac, vector<int> &star) 
{
    for (int i = 0; i < mac.size(); ++i) {
        if (mac[i] == vertex) return false;
    }
    for (int i = 0; i < star.size(); ++i) {
        if (star[i] == vertex) return false;
    }
    return true;
}

void Dijkstra(int start, bool isMac)
{
    if (isMac) {
        fill(dist_m.begin(), dist_m.end(), INF);
        dist_m[start] = 0;
    } else {
        fill(dist_s.begin(), dist_s.end(), INF);
        dist_s[start] = 0;
    }
    pq.push({start, 0});

    while (!pq.empty()) {
        int node = pq.top().node;
        int cost = pq.top().cost;
        pq.pop();

        for (int i = 0; i < map[node].size(); ++i) {
            int nextNode = map[node][i].first;
            int nextCost = map[node][i].second;
            if (isMac) {
                if (dist_m[nextNode] > dist_m[node] + nextCost) {
                    dist_m[nextNode] = dist_m[node] + nextCost;
                    pq.push({nextNode, dist_m[nextNode]});
                }
            } else {
                if (dist_s[nextNode] > dist_s[node] + nextCost) {
                    dist_s[nextNode] = dist_s[node] + nextCost;
                    pq.push({nextNode, dist_s[nextNode]});
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    int v, e;
    cin >> v >> e;
    for (int i = 1; i <= e; ++i) {
        int u, v, w; cin >> u >> v >> w;
        map[u].push_back(make_pair(v, w));
        map[v].push_back(make_pair(u, w));
    }

    int m, s, x, y;
    cin >> m >> x; vector<int> mac(m+1);
    for (int i = 1; i <= m; ++i) cin >> mac[i];

    cin >> s >> y; vector<int> star(s+1);
    for (int i = 1; i <= s; ++i) cin >> star[i];

    for (int i = 1; i <= m; ++i) {
        Dijkstra(mac[i], true);
        for (int j = 1; j <= s; ++j) {
            Dijkstra(star[j], false);
            for (int k = 1; k <= v; ++k) {
                if (dist_m[k] <= x && dist_s[k] <= y) {
                    res.push({k, x + y});
                }
            }
        }
    }

    while (true) {
        int vertex = res.top().node;
        if (isHouse(vertex, mac, star)) {
            cout << res.top().cost << endl;
            break;
        } else {
            res.pop();
        }
    }

    return 0;
}

模範解答

#include <iostream>
#include <vector>
#include <queue>
#define INF 100000000
using namespace std;

vector<pair<int, int> > map[10001];
vector<int> dist_m(10001, INF);
vector<int> dist_s(10001, INF);

class Info {
public:
    int node, cost;

    bool operator<(const Info &rhs) const {
        return this->cost > rhs.cost;
    }
};
priority_queue<Info> pq;

void Dijkstra(vector<int> &dist)
{
    while (!pq.empty()) {
        int node = pq.top().node;
        int cost = pq.top().cost;
        pq.pop();
        
        for (int i = 0; i < map[node].size(); ++i) {
            int nextNode = map[node][i].first;
            int nextCost = map[node][i].second;
            if (dist[nextNode] > dist[node] + nextCost) {
                dist[nextNode] = dist[node] + nextCost;
                pq.push({nextNode, dist[nextNode]});
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    int v, e;
    cin >> v >> e;
    for (int i = 1; i <= e; ++i) {
        int u, v, w; cin >> u >> v >> w;
        map[u].push_back(make_pair(v, w));
        map[v].push_back(make_pair(u, w));
    }
    
    int m, x, s, y;
    cin >> m >> x;
    for (int i = 1; i <= m; ++i) {
        int tmp; cin >> tmp;
        dist_m[tmp] = 0;
        pq.push({tmp, 0});
    };
    Dijkstra(dist_m);
    
    cin >> s >> y;
    for (int i = 1; i <= s; ++i) {
        int tmp; cin >> tmp;
        dist_s[tmp] = 0;
        pq.push({tmp, 0});	// <---------- 두번 째
    };
    Dijkstra(dist_s);

    int mini = 2*INF;
    for (int i = 1; i <= v; ++i) {
        if (dist_m[i] && dist_s[i] && dist_m[i] <= x && dist_s[i] <= y) {  // <--- 세번 째
            mini = min(mini, dist_m[i] + dist_s[i]);
        }
    }

    if (mini == 2*INF) cout << -1 << endl;
    else cout << mini << endl;

    return 0;
}