重み付き有向グラフにおいて、特定の始点から各頂点への最短距離を求める単一始点最短経路問題。ここでは、隣接行列を入力とし、優先度付きキューを用いたDijkstra法の実装を示す。構造体を使わず、配列とペアのみで構成する。

入力仕様

1行目に頂点数 n と始点番号 s を指定する。続く n 行の各行に n 個の整数を並べ、隣接行列を表現する。行列の要素が正の整数の場合、対応する有向辺の重みを示す。0は辺がないことを表し、対角成分は常に0とする。

出力仕様

始点以外の各頂点への最短距離を順に出力する。到達不能な頂点には -1 を出力する。

入力例

4 1
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0

出力例

6 4 7 

実装

グラフを隣接リストで管理し、最小ヒープによる貪欲な頂点選択で距離を確定していく。配列 head、to、cost、nxt を用いて連結リストを構築し、メモリ効率を図る。

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 100010;
const int MAXE = 200020;
const int LINF = 0x3f3f3f3f;

int head[MAXV], nxt[MAXE], edTo[MAXE], edW[MAXE];
int used[MAXV], d[MAXV];
int tot = 0;

void ins(int u, int v, int w) {
    edTo[tot] = v;
    edW[tot] = w;
    nxt[tot] = head[u];
    head[u] = tot++;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, src;
    cin >> n >> src;
    
    fill(head, head + n + 1, -1);
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int w; 
            cin >> w;
            if (w > 0) ins(i, j, w);
        }
    }
    
    fill(d, d + n + 1, LINF);
    d[src] = 0;
    
    using Node = pair;
    priority_queue pq;
    pq.push({0, src});
    
    while (!pq.empty()) {
        auto [du, u] = pq.top(); 
        pq.pop();
        
        if (used[u]) continue;
        used[u] = 1;
        
        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = edTo[e];
            int nd = du + edW[e];
            if (nd < d[v]) {
                d[v] = nd;
                pq.push({nd, v});
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        if (i == src) continue;
        if (d[i] == LINF) cout << -1;
        else cout << d[i];
        if (i < n) cout << ' ';
    }
    cout << '\n';
    
    return 0;
}

この実装では、priority_queue に greater を指定することで最小ヒープ化し、確定済み頂点の重複プッシュを used 配列でスキップする。C++17の構造化束縛を活用して可読性を高めている。