最短路之Dijkstra算法

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define INF 0x3f3f3f3f
using namespace std;
int map[1005][1005];
int dis[1005],book[1005];
int main() {
  int n,m;
  while(cin>>m>>n) {
    memset(dis,0,sizeof(dis));
    memset(book,0,sizeof(book));
    memset(map,INF,sizeof(map));
    for(int i=1; i<=n; i++)
      map[i][i]=0;//自己到自己为0，其他初始化为正无穷
    for(int i=1; i<=m; i++) {
      int x,y,z;
      cin>>x>>y>>z;
      map[x][y]=z;
    }
    for(int i=1; i<=n; i++)
      dis[i]=map[1][i];//以1为源，存储1到别的点的“估计值”
    book[1]=1;//点1是确定值
    for(int i=1; i<=n-1; i++) {
      int min=INF;
      int u=1;
      for(int j=1; j<=n; j++) {
        if(book[j]==0 && dis[j]<min) {
          min=dis[j];
          u=j;//在估计值中选取权最小的
        }
      }
      book[u]=1;//把1到别的点的“估计值”的权最小的点变成确定值
      for(int j=1; j<=n; j++) {
        if(map[u][j]<INF ) {//找到与u相连的点，设为x
          if(dis[j]>dis[u]+map[u][j] && book[j]==0 )//更新估计值,确定值不变
            dis[j]=dis[u]+map[u][j];//1->u,u->x的线路比1->x的线路优，所以更新1->x的线路
        }
      }
    }
    cout<<dis[n]<<endl;//dis[n]即1->x的最短路
  }
}