[算法模板]dijkstra单源最短路径

#include <iostream>
#include <cstring>
using namespace std;
/*
  1 2 2
  1 3 5
  2 3 2
  2 4 6
  3 4 7
  3 5 1
  4 3 2
  4 5 4
 */
 const int N = 99999;
 typedef struct{
     int vex[100];
     int edge[100][100];
     int vexnum;
     int edgenum;
 }maps;
 int dist[100];
 int pervious[100];
 bool flag[100];

 int find_u(maps g,int u){
   for(int i = 1;i <= g.vexnum; i++){
     if(g.vex[i] == u) return i;
   }
   return -1;
 }

 void create_map(maps &g){
  g.vexnum = 5;
  g.edgenum = 8;


  for(int i = 1; i <= g.vexnum; i++){
    for(int j = 1; j <= g.vexnum;j++){
      g.edge[i][j] = N;
    }
  }

  int u,v,w;
  for(int i = 1; i <= g.vexnum;i++){
    cin >> u;
    g.vex[i] = u;
  }
  cout <<"input vex is ok!" <<endl;
  for(int i = 1; i <= g.edgenum;i++){
    cin >>u >>v >>w;
    u = find_u(g,u);
    v = find_u(g,v);
    if(u != -1 && v != -1){
       g.edge[u][v] = w;
    }else{
      cout << "error" <<endl;
      i--;
    }
  }

  cout <<"input edge is ok"<<endl;
  
 }

 void dijkstra(maps g,int u){
   flag[u] = true;
  
   for(int i = 1; i <= g.vexnum;i++){
      if(g.edge[u][i] != N){
        dist[i]  = g.edge[u][i];
        pervious[i] = u;
      }else {
        dist[i] = N; 
        pervious[i] = -1;
      }
   }
    dist[u] = 0;
    for(int i = 1; i< g.vexnum;i++){
      int temp =N;
      int t = u;
      for(int j = 1; j < g.vexnum;j++){
        if(!flag[j] && dist[j] < temp){
          temp = dist[j];
           t = j;
        }
      }

      if(t == u) return;
      flag[t] = true;
      for(int j= 1; j < g.vexnum; j++){
        if(!flag[j] && g.edge[t][j]!=N){
          if(dist[j] > (dist[t]+g.edge[t][j])){
            dist[j] = dist[t]+g.edge[t][j];
            pervious[j] = t;
          }
        }

      }
    }

 }
 int main(){
   maps g; // map
   memset(flag,false,sizeof(flag));
   memset(dist,-1,sizeof(dist));
   memset(pervious,-1,sizeof(pervious));
   create_map(g);
   cout << g.vexnum;
   cout << "please input u:";
   int u;
   cin >> u;
   dijkstra(g,find_u(g,u));
   cout << "start:" <<u << endl;
   for(int i  = 1; i < g.vexnum;i++){
     int temp = find_u(g,i);
     cout << u <<"  to  "<< i << "  " << dist[temp]<<endl;
   }


 }