解いた問題

3/29/2013

SRM551 Div1 Medium

450

変更の回数をコストにしてダイクストラする。

  1. class ColorfulWolves {  
  2. public:  
  3.   int getmin(vector <string> cm)  
  4.   {  
  5.     const int N = 50 + 1;  
  6.   
  7.     bool g[N][N];  
  8.     fill(&g[0][0], &g[N - 1][N - 1] + 1, false);  
  9.   
  10.     const int V = cm.size();  
  11.   
  12.     for (int i = 0; i < V; ++i) {  
  13.       for (int j = 0; j < V; ++j) {  
  14.         g[i][j] = (cm[i][j] == 'Y');  
  15.       }  
  16.     }  
  17.   
  18.     map<intint> cost;  
  19.     set<int> vis;  
  20.     priority_queue< pair<intint> > q;  
  21.   
  22.     for (q.push(make_pair(0, 0)); q.size(); ) {  
  23.       int curr = q.top().second;  
  24.       int change = -1 * q.top().first;  
  25.       q.pop();  
  26.       if (vis.count(curr)) continue;  
  27.       vis.insert(curr);  
  28.       cost[curr] = change;  
  29.       int cnt = 0;  
  30.       for (int next = 0; next < N; ++next) {  
  31.         if (g[curr][next] && !vis.count(next)) {  
  32.           q.push(make_pair(-(change + cnt), next));  
  33.         }  
  34.         if (g[curr][next]) ++cnt;  
  35.       }  
  36.     }  
  37.     return vis.count(V - 1) ? cost[V - 1] : -1;  
  38.   }  
  39. };