贪心算法之用优先队列解决最短路径问题（Dijkstra算法）

   

    

     

      

     
     

      

       #include <iostream>
      
     
    

     

      

     
     

      

       #include <cstdio>
      
     
    

     

      

     
     

      

       #include <stack>
      
     
    

     

      

     
     

      

       #include <cstring>
      
     
    

     

      

     
     

      

       #include <queue>
      
     
    

     

      

     
     

      

       #include <cstdlib>
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       using namespace std;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

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

     

      

     
     

      

       const int MAX_CITY_NUM = 100;
      
     
    

     

      

     
     

      

       //节点权值的最大值
      
     
    

     

      

     
     

      

       const int MAX_POLICY = 1e7;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       /*
      
     
    

     

      

     
     

      

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

     

      

     
     

      

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

     

      

     
     

      

       */
      
     
    

     

      

     
     

      

       struct Node
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      

       	//value是节点值，然后min_dist是源点到这个节点的最短路径
      
     
    

     

      

     
     

      

       	int value, min_dist;
      
     
    

     

      

     
     

      

       	//注意这里前