問題1：都市間の最短経路探索

この問題では、都市間の輸送経路における最短距離を求めます。幅優先探索を応用したアルゴリズムを実装します。

#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <climits>
using namespace std;

// グラフの辺を表す構造体
struct Connection {
    int destination;  // 接続先の都市
    int cost;         // 移動コスト
    Connection (int dest, int c) : destination(dest), cost(c) {}  // コンストラクタ
};

int main() {
    int cityCount, routeCount, fromCity, toCity, travelCost;
    cin >> cityCount >> routeCount;
    vector<list<Connection>> cityNetwork(cityCount + 1);  // 隣接リスト表現
    
    // 経路情報の読み込み
    for (int i = 0; i < routeCount; i++) {
        cin >> fromCity >> toCity >> travelCost;
        // fromCityからtoCityへの経路を追加
        cityNetwork[fromCity].push_back(Connection(toCity, travelCost));
    }
    
    int origin = 1;  // 出発都市
    int destination = cityCount;  // 目的都市
    
    // 最短距離配列の初期化
    vector<int> shortestDistance(cityCount + 1, INT_MAX);
    shortestDistance[origin] = 0;
    
    // キューを用いた幅優先探索
    queue<int> cityQueue;
    cityQueue.push(origin);
    
    while (!cityQueue.empty()) {
        int currentCity = cityQueue.front();
        cityQueue.pop();
        
        // 現在の都市から接続されている全都市を探索
        for (Connection conn : cityNetwork[currentCity]) {
            int source = currentCity;
            int target = conn.destination;
            int expense = conn.cost;
            
            // より短い経路が見つかった場合
            if (shortestDistance[target] > shortestDistance[source] + expense) {
                shortestDistance[target] = shortestDistance[source] + expense;
                cityQueue.push(target);
            }
        }
    }
    
    // 結果出力
    if (shortestDistance[destination] == INT_MAX) 
        cout << "unconnected" << endl;
    else 
        cout << shortestDistance[destination] << endl;
}

問題2：負の閉路を含む都市間輸送

この問題では、ベルマン・フォード法を用いて最短経路を求めるとともに、負の閉路の存在を検出します。

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int cityCount, routeCount, origin, destination, cost;
    cin >> cityCount >> routeCount;
    
    vector<vector<int>> transportRoutes;
    for (int i = 0; i < routeCount; i++) {
        cin >> origin >> destination >> cost;
        transportRoutes.push_back({origin, destination, cost});
    }
    
    int startCity = 1;
    int endCity = cityCount;
    
    // 最短距離配列の初期化
    vector<int> minCost(cityCount + 1, INT_MAX);
    minCost[startCity] = 0;
    
    bool hasNegativeCycle = false;
    
    // ベルマン・フォード法の実装
    for (int iteration = 1; iteration <= cityCount; iteration++) {
        for (vector<int> &route : transportRoutes) {
            int from = route[0];
            int to = route[1];
            int price = route[2];
            
            if (iteration < cityCount) {
                // 通常の緩和操作
                if (minCost[from] != INT_MAX && 
                    minCost[to] > minCost[from] + price) {
                    minCost[to] = minCost[from] + price;
                }
            } else {
                // 負の閉路の検出
                if (minCost[from] != INT_MAX && 
                    minCost[to] > minCost[from] + price) {
                    hasNegativeCycle = true;
                }
            }
        }
    }
    
    // 結果出力
    if (hasNegativeCycle) 
        cout << "circle" << endl;
    else if (minCost[endCity] == INT_MAX) 
        cout << "unconnected" << endl;
    else 
        cout << minCost[endCity] << endl;
}

問題3：中継回数制限付き都市間輸送

この問題では、中継地点の数に制限がある条件下での最短経路を求めます。制限付きベルマン・フォード法を実装します。

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int cityCount, routeCount, start, end, maxStops;
    int from, to, weight;
    cin >> cityCount >> routeCount;
    
    vector<vector<int>> routes;
    for (int i = 0; i < routeCount; i++) {
        cin >> from >> to >> weight;
        routes.push_back({from, to, weight});
    }
    
    cin >> start >> end >> maxStops;
    
    // 最短距離配列の初期化
    vector<int> shortestPath(cityCount + 1, INT_MAX);
    shortestPath[start] = 0;
    
    // 前回の反復結果を保存する配列
    vector<int> previousPath(cityCount + 1);
    
    // 制限付き反復処理
    for (int step = 1; step <= maxStops + 1; step++) {
        previousPath = shortestPath;  // 前回の結果をコピー
        
        for (vector<int> &route : routes) {
            int origin = route[0];
            int destination = route[1];
            int cost = route[2];
            
            // 前回の反復結果を用いて緩和操作
            if (previousPath[origin] != INT_MAX &&
                shortestPath[destination] > previousPath[origin] + cost) {
                shortestPath[destination] = previousPath[origin] + cost;
            }
        }
    }
    
    // 結果出力
    if (shortestPath[end] == INT_MAX) 
        cout << "unreachable" << endl;
    else 
        cout << shortestPath[end] << endl;
}