贪心算法之最短路径问题（Dijkstra算法）

   

    

     

      

     
     

      

       #include <iostream>
      
     
    

     

      

     
     

      

       #include <cstdio>
      
     
    

     

      

     
     

      

       #include <stack>
      
     
    

     

      

     
     

      

       #include <string>
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       using namespace std;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       /*
      
     
    

     

      

     
     

      

       一定要记得如果初始化矩阵的话，肯定需要一个变量保存长和宽的最大值，
      
     
    

     

      

     
     

      

       如果看到权重的话，肯定是需要有个变量保存最大值的权重
      
     
    

     

      

     
     

      

       */
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       //城市的节点数目的最大值
      
     
    

     

      

     
     

      

       const int MAX_CITY_NUM = 100;
      
     
    

     

      

     
     

      

       //节点权值的最大值
      
     
    

     

      

     
     

      

       const int MAX_POLICY = 1e7;
      
     
    

     

      

     
     

      

       //初始化权重矩阵
      
     
    

     

      

     
     

      

       int map[MAX_CITY_NUM][MAX_CITY_NUM];
      
     
    

     

      

     
     

      

       //源点到各个顶点的最短具体数组
      
     
    

     

      

     
     

      

       int dist[MAX_CITY_NUM];
      
     
    

     

      

     
     

      

       //下标表示当前节点值，然后值保