[BOJ]1719号:宅配便(C++)

14866 ワード
cpp algorithm baekjoon テキストリンク
質問リンク:白俊1719号。
[質問へのアクセス]
基本的な解答は複数の線分で解答され、最初に通る集合点を見つけるため、最短経路を通る経路を保存します.
私はans配列に格納します.ans[next]=curはnextが来る前の経路がcurであることを意味します.
ex)ans[2]=1は1から2までの経路
  • arrバックグラウンドに情報を格納します.
  • のエストラ関数に入ります.
  • キューの優先度を昇順に設定します.
  • の最短経路を探索するとともに、ansアレイに全経路を格納する.
  • 最短経路探索が完了すると,正解を出力する必要がある.
  • 現在のセット(i)と探索開始点(num)が同じであれば、-が出力される.
  • の現在の集合点の経路(ans[i])がナビゲーション開始点(num)と同じである場合、현재 집하장が出力される.
  • 以外の場合、ナビゲーションの開始点と同じ場合になるまでクラスタに遡る.
    • [ソースコード]
    #include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;
int n, m;
typedef pair<int, int> p;
vector<p> arr[201];
int dir[201];
int ans[201];

void dijsktra(int num) {
    memset(dir, 200000, sizeof(dir));
    dir[num] = 0;
    priority_queue<p, vector<p>, greater<p>> pq;
    pq.push({0, num});
    while(!pq.empty()) {
        int cur = pq.top().second;
        pq.pop();

        for(int i=0 ; i<arr[cur].size() ; i++) {
            int next = arr[cur][i].first;
            if(dir[next]>dir[cur]+arr[cur][i].second) {
                ans[next] = cur; // 경로를 저장
                dir[next] = dir[cur]+arr[cur][i].second;
                pq.push({dir[next], next});
            }
        }
    }

    for(int i=1 ; i<=n ; i++) {
        if(i==num) { // 현재 집하장과 탐색 시작점이 같으면 자기 자신이므로 - 출력
            cout << "- ";
        } else if(ans[i]==num) { // 현재 집하장의 전 경로(ans[i])가 탐색 시작점과 같으면 해당 집하장 출력
            cout << i << " ";
        } else { // 그 외의 경우
            int now = i;
            while(true) {
                if(ans[now]==num) {
                    cout << now << " ";
                    break;
                } else {
                    now = ans[now]; // 전 경로로 거슬러 올라감
                }
            }
        }
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i=0 ; i<m ; i++) {
        int u,v,a;
        cin >> u >> v >> a;
        arr[u].push_back({v, a});
        arr[v].push_back({u, a});
    }
    for(int i=1 ; i<=n ; i++) {
        dijsktra(i);
    }

    return 0;
}
    Webセキュリティに関するいくつかの防犯措置
    位置データ