AOJ Single Source Shortest Path I（单源最短路径）

链接：https://vjudge.net/problem/Aizu-ALDS1_12_B
思路：与最小生成树写法类似，只是判断条件有所更改。最小生成树是搜索到每个点最小的距离然后更新，最短路径则是通过
if(d[v]>d[u]+M[u][v])
d[v] = d[u] + M[u][v];
来更新最短路径，相邻点加上两点路径若小于原来的最短路径，则更新。

其余类似请参考最小生成树：https://www.jianshu.com/p/e07bfcb7b82c

代码：
#include<iostream>
using namespace std;
static const int MAX = 100;
static const int INFTY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n,M[MAX][MAX];

void dijkstra(){
int minv;
int d[MAX],color[MAX];

for(int i=0;i<n;i++){
d[i] = INFTY;
color[i] = WHITE;
}

color[0] = GRAY;
d[0] = 0;

while(1){
minv = INFTY;
int u = -1;
for(int i=0;i<n;i++){
if(minv>d[i]&&color[i]!=BLACK){
u = i;
minv = d[i];
}
}
if(u==-1)break;
color[u] = BLACK;

for(int v=0;v<n;v++){
if(color[v]!=BLACK&&M[u][v]!=INFTY){
if(d[v]>d[u]+M[u][v]){//如果相邻点两步距离之和小于原来的一步，则更新最小步数。
d[v] = d[u] + M[u][v];
color[v] = GRAY;
}
}
}
}
for(int i=0;i<n;i++){
cout<<i<<" "<<(d[i]==INFTY?-1:d[i])<<endl;
}
}

int main(){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
M[i][j] = INFTY;
}
}
int k,c,u,v;
for(int i=0;i<n;i++){
cin>>u>>k;
for(int j=0;j<k;j++){
cin>>v>>c;
M[u][v] = c;
}
}
dijkstra();
return 0;
}