hdu2612(dijkstra)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2612

题意：给出一个n*m的矩阵，' . ' 表示可以走的路， ' # '表示不能走的路，’ @'表示KCF， ‘Y' , 'M' 表示两个人开始的位置，

他们可以走到相邻的路，每走一步需要11分钟，问他们要在KCF见面，最少需要花多少时间。

思路：我们可以把矩阵化成图，再通过dijkstra求出Y和M到各个KCF的距离，然后找对应和最小的就是答案啦。

注意这里矩阵最大为200*200，所以有40000个节点，我们需要对dijkstra做堆优化，不然能会超时。

代码：

 #include <iostream>

 #include <stdio.h>

 #include <queue>

 #include <string.h>

 #define MAXN 210

 using namespace std;

 vector<pair<int, int> > vec[MAXN*MAXN];//***记录图

 bool vis[MAXN*MAXN];//***标记该点是否在堆中

 const int inf=0x3f3f3f3f;

 char mp[MAXN][MAXN];

 int n, m, pos=, s1=, s2=, a[MAXN*MAXN];

 struct node{//***重载比较符使优先队列非升序排列

     int point, value;

     friend bool operator< (node a, node b){

         return  a.value>b.value;

     }

 };

 void get_vec(){//建图

     for(int i=; i<MAXN*MAXN; i++){

         vec[i].clear();

     }

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

         for(int j=; j<m; j++){

             if(mp[i][j]=='@'){

                 a[pos++]=i*m+j;

             }else if(mp[i][j]=='Y'){

                 s1=i*m+j;

             }else if(mp[i][j]=='M'){

                 s2=i*m+j;

             }

             if(mp[i][j]!='#'){

                 int u=i*m+j;

                 if(mp[i+][j]!='#'&&i+<n){

                     int v=(i+)*m+j;

                     vec[u].push_back({v, });

                     vec[v].push_back({u, });

                 }

                 if(mp[i][j+]!='#'&&j+<m){

                     int v=i*m+j+;

                     vec[u].push_back({v, });

                     vec[v].push_back({u, });

                 }

             }

         }

     }

 }

 int &dijkstra_heap(int s, int dist[MAXN*MAXN]){//最短路求源点到其他点的距离

     priority_queue<node> q;

     memset(vis, false, sizeof(vis));

     dist[s]=;

     q.push({s, dist[s]});

     while(!q.empty()){

         node u=q.top();

         int point=u.point;

         q.pop();

         if(vis[point]){

             continue;

         }else{

             vis[point]=true;

         }

         for(int i=; i<vec[point].size(); i++){

             int v=vec[point][i].first;

             int cost=vec[point][i].second;

             if(!vis[v]&&dist[v]>dist[point]+cost){//***松驰操作

                 dist[v]=dist[point]+cost;

                 q.push({v, dist[v]});

             }

         }

     }

 }

 int main(void){

     while(scanf("%d%d", &n, &m)!=EOF){

         int dist1[MAXN*MAXN], dist2[MAXN*MAXN];//***记录源点此时到 i 的最短距离

         memset(dist1, 0x3f, sizeof(dist1));

         memset(dist2, 0x3f, sizeof(dist2));

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

             scanf("%s", mp[i]);

         }

         pos=;

         get_vec();

         dijkstra_heap(s1, dist1);

         dijkstra_heap(s2, dist2);

         int ans=inf;

         for(int i=; i<pos; i++){

             ans=min(dist1[a[i]]+dist2[a[i]], ans);

         }

         cout << ans* << endl;

     }

     return ;

 }

巴特西

hdu2612(dijkstra)

最新文章

热门文章