[HDU] 1874 畅通工程续基本单源路径粗糙实现

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1874

方法：使用邻接表，将两个点之间的所有边都用一条最小费用的边来代表。然后用这些边来建立图并调用DIJKSTRA，最后判断到目标定点的距离是不是正无穷，不是正无穷的值就是最小路径的费用权值。

感想：用数组每次排序没有在选择的点的方法来模拟优先队列不好，以后要用堆来模拟。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
int const MAX =0x3f3f3f3f;
int cityCount,roadsCount;
int matrix[201][201];
struct cityDistance
{
    int city;
    int _distance;
};
cityDistance distances[201];
bool visisted[201];
int cmp( cityDistance a, cityDistance b) 
{
    if (a._distance < b._distance) 
        return 1;    
    else return 0; 
}
int main()
{     
    while(scanf("%d %d",&cityCount,&roadsCount)!=EOF)
    {
         int st,ed,cost;
         memset(matrix,MAX,sizeof(matrix));
         memset(visisted,false,sizeof(visisted));
         for(int i =0;i<cityCount;i++)
         {
            distances[i].city=i;
            distances[i]._distance = MAX;
            matrix[i][i]=0;
         }
         for(int i=0;i<roadsCount;i++)
         {
            scanf("%d %d %d",&st,&ed,&cost);
            if(cost<matrix[st][ed])
                matrix[st][ed] = matrix[ed][st] =cost;
         }
         scanf("%d %d",&st,&ed);    
         if(st==ed)
             cout<<0<<endl;
         else
         {
             distances[st]._distance = 0;
             int t_c=0;
             sort(distances+t_c,distances+cityCount,cmp);
     
             while(t_c<cityCount)
             {
                 int t = distances[t_c].city;
                 int t_dist =  distances[t_c]._distance ; 
                  t_c++;
                 visisted[t] = true;
                 for(int i=0;i<cityCount;i++)
                 {
                     if(!visisted[distances[i].city] && matrix[t][distances[i].city]!=MAX)
                         distances[i]._distance = t_dist+matrix[t][distances[i].city] < distances[i]._distance ? t_dist+matrix[t][distances[i].city] : distances[i]._distance;
                 }
                 sort(distances+t_c,distances+cityCount,cmp);//以后这里要改成堆  不用stl优先队列的堆 是自己写的堆
             }
             int re =0;
             for(int i=0;i<cityCount;i++)
             {
                 if(distances[i].city == ed)
                     re = distances[i]._distance;
             }
             if(re ==MAX)
                 cout<<-1<<endl;
             else
                cout<<re<<endl;
         }
    }
    return 0;
}