【图】单源最短路径dijkstra

O（n^2）级C算法，简易复习用

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int INF = 1000000000;
const int MAXN = 1000;

int n, m;
int v[MAXN], d[MAXN], G[MAXN][MAXN];

int main() {
  scanf("%d%d", &n, &m);
  for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      G[i][j] = INF;
  for(int i = 0; i < m; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    G[u][v] = w;
  }
  
  memset(v, 0, sizeof(v));
  for(int i = 0; i < n; i++) d[i] = (i==0 ? 0 : INF); 
  for(int i = 0; i < n; i++) {
    int x, m = INF;
    for(int y = 0; y < n; y++) if(!v[y] && d[y]<=m) m = d[x=y]; //选出所有未被遍历的点中d值最小的节点x，即到始点最短的点 
    v[x] = 1;//标记点x 
    for(int y = 0; y < n; y++) d[y] = min(d[y], d[x] + G[x][y]);//更新 
  }
  
  for(int i = 0; i < n; i++)
    printf("d[%d] =  %d\n", i, d[i]);
  return 0;
}
#include<stdio.h>
#include<s