ベルマンフォード法とダイクストラ法をvectorで実装

ベルマンフォード法

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


struct Edge {
    int to, cost;

};
typedef vector<vector<Edge> > AdjList;  // 隣接リストの型
AdjList graph;

const int INF = 1000000;

vector<int> dist;


bool bellman_ford(int n, int s){
    dist = vector<int>(n,INF);
    dist[s] = 0;
    for(int i=0;i<n;i++){
        for(int v=0;v<n;v++){
            for(int k=0;k<graph[v].size();k++){
                Edge e = graph[v][k];
                if(dist[v] != INF && dist[e.to] > dist[v] + e.cost){
                    dist[e.to] = dist[v] + e.cost;
                    if(i == n-1) return true;
                }
            }
        }
    }
    return false;
}

int main(void){
    int n, m;
    cin >> n >> m;

    graph = AdjList(n);

    for(int i=0;i<m;i++){
        int from, to, cost;
        cin >> from >> to >> cost;
        graph[from].push_back((Edge){to,cost});
    }

    bellman_ford(n,0);

    for (int i = 1; i < n; i++){
       if(dist[i] != INF){
           cout << "0から" << i << "へのコスト:" << dist[i] << endl;
       }
    }
    return 0;
}

ダイクストラ法

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> P;

struct edge {
    int to, cost;
};
typedef vector<vector<edge> > AdjList;

AdjList graph;

const int INF = 10000000;
vector<int> dist;

void dijkstra(int n, int s){
    dist = vector<int>(n,INF);
    dist[s] = 0;
    priority_queue<P, vector<P>, greater<P> > que;
    que.push(P(0,s));

    while(!que.empty()){
        P p = que.top();
        que.pop();
        int v = p.second;
        if(dist[v] < p.first){
            continue;
        }
        for(int i=0;i < graph[v].size();i++){
            edge e = graph[v][i];
            if(dist[e.to] > dist[v] + e.cost){
                dist[e.to] = dist[v] + e.cost;
                que.push(P(dist[e.to],e.to));
            }
        }
    }
}


int main(void){
    int n, m;
    cin >> n >> m;

    graph = AdjList(n);

    for(int i=1;i<m;i++){
        int from, to, cost;
        cin >> from >> to >> cost;
        graph[from].push_back((edge){to,cost});
    }
    dijkstra(n,0);

    for(int i=0;i<n;i++){
        if(dist[i] != INF){
            cout << "0から" << i << "へのコスト:" << endl;
        }
    }
    return 0;
}

参考

最短経路問題（ベルマンフォード法・ワーシャルフロイド法） - アルゴリズム講習会

蟻本