読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

単一始点最短経路 dijkstra法

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 100; 
static const int WHITE = 0;//未踏
static const int GRAY  = 1;//確定している点と隣接
static const int BLACK = 2;//確定
static const int INF = 1<<21;

int M[MAX_N][MAX_N] = {0};//隣接行列
int d[MAX_N] = {0};//最短経路コスト
int color[MAX_N] = {WHITE};
int n,u,k,c,v;

void dijkstra(int s){
    int mincost;
    //初期化: 全ての頂点uに対してcolor[u]をWHITE, d[u]をINF, d[s]=0, p[s]=-1;
    for(int u=0;u<n;u++){
        color[u] = WHITE;
        d[u] = INF;
    }
    d[s]=0;
    color[0] = GRAY;

    while(true){
        mincost = INF;
        int u = -1;
        for(int i=0;i<n;i++){
            if(color[i]!=BLACK && d[i]<mincost){
                mincost = d[i];
                u = i;
            }
        }
        if(u==-1){
            break;
        }
        color[u]=BLACK;
        
        for(int v=0;v<n;v++){
            if(color[v]!=BLACK && M[u][v]!=INF){
                if(d[v]>d[u]+M[u][v]){
                    d[v]=d[u]+M[u][v];
                    color[v]=GRAY;
                }
            }
        }
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){//隣接グラフは重みINFの辺に初期化しておく
        for(int j=0;j<n;j++){
            M[i][j] = INF;
        }
    }
    for(int i=0;i<n;i++){//隣接リストから隣接グラフへ書き換える
        cin>>u>>k;
        for(int j=0;j<k;j++){
            cin>>c>>v;
            M[u][c] = M[c][u] = v;
        }
    }
    //始点は0
    dijkstra(0);
    for(int i=0;i<n;i++){
        cout<<i<<" "<<d[i]<<endl;
    }
    return 0;
}