POJ 1062 ( dijkstra )

一个中文题，一个多月之前我做过，当时我是用搜索写的，不过苦于卡在无法确定等级关系，所以就错了。

看了别人的博客后，我还是不是很理解所谓的枚举等级是怎样枚举，因为我觉得在递归的时候，我真的不知道怎么枚举等级。

然后今天在看到了一个人写的，枚举等级怎么枚举，我才发现我用那个搜索写的话，我还是有问题。所以我就用这个新学的dijkstra写

所谓的枚举等级，就是以每一个等级都视为最低等级来进行枚举。

比如等级限制1，而那个酋长的等级是3，那么你就应该枚举2-4，和3-5的等级的人。

 #include <stdio.h>

 #include <string.h>

 #define inf 9999999

 int m,n;

 int price[],d[];

 int graph[][];

 int rank[];

 bool mark[],limit[];

 int dijkstra()

 {

     int result = inf;

     int k,dis;

     memset(mark,false,sizeof(mark));

     d[  ] = ;

     for(int i =  ; i <= n ; i++)

         d[ i ] = inf;

     for(int i =  ; i <= n ; i++)     //dijkstra是这个循环

     {

         k = ;

         dis = inf;

         for(int j= ; j <= n ;j++)

             if(!mark[ j ] && d[ j ] <= dis && limit[ j ])

             {

                 k = j;

                 dis = d[ j ];

             }

             mark[ k ] = true;

             for(int j =  ; j <= n ; j++)

             {

                 if(limit[ j ] && d[ j ] > d[ k ] + graph[ k ][ j ])

                     d[ j ] = d[ k ] + graph[ k ][ j ];

             }

     }

     for(int i =  ;i <= n ;i++)

     {

         d[ i ] += price[ i ];    //d[i] 是存储着交换i次后的价钱。

         if(d[ i ] < result)

             result = d[ i ];

     }

     return result;

 }

 int main()

 {

     int x,t,v,ans = inf;

     scanf("%d%d",&m,&n);

     for(int i =  ; i <= n ; i++)      //进行构图。

         for(int j = ;j <= n ; j++)

             if( i == j )

                 graph[ i ][ j ] = ;

             else

                 graph[ i ][ j ] = inf;

     for(int i =  ; i <= n ; i++)

     {

         scanf("%d%d%d",&price[i],&rank[i],&x);

         for(int j =  ; j < x ; j++)

         {

             scanf("%d%d",&t,&v);

             graph[ i ][ t ] = v;

         }

     }

     for(int i =  ; i <= m ; i++)      //这里就是枚举等级，把可以和酋长交换的人进行标记，然后进行最短路的寻找。

     {

         memset(limit,,sizeof(limit));

         for(int j =  ; j <= n ; j++)

             if(rank[ j ] >= rank[  ] - m + i && rank[ j ] <= rank[  ] + i)

                 limit[ j ] = true;

             t = dijkstra();

             if(ans > t)

                 ans = t;

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

POJ 1062 ( dijkstra )

最新文章

热门文章