51nod 1445 变色DNA(dij)

看了相关讨论再去用最短路：val[i][j]之间如果是‘Y’，说明i可以到达j，并且i到达j的代价是i那行 1到j-1 里面‘Y’的数量。

最后，求 0到n-1的最短路。

感觉读懂了题意就真的简单了。。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #define CLR(a,b) memset((a),(b),sizeof((a)))

 using namespace std;

 const int inf = 0x3f3f3f3f;

 const int N = ;

 int d[N], vis[N];

 char mp[N];

 int n;

 struct qnode{

     int v, c;

     qnode(int _v = ,int _c = ):v(_v),c(_c) {}

     bool operator < (const qnode &r)const{

         return r.c < c;

     }

 };

 vector<int>E[N];

 void dij(){

     priority_queue<qnode>q;

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

         d[i] = inf;

         vis[i] = ;

     }

     d[] = ;

     q.push(qnode(, ));

     while(!q.empty()){

         qnode t = q.top(); q.pop();

         int u = t.v;

         if(vis[u])

             continue;

         vis[u] = ;

         for(int i = ; i < E[u].size(); ++i){

             int v = E[u][i];

             if(!vis[v] && d[u] + i < d[v]){

                 d[v] = d[u] + i;

                 q.push(qnode(v, d[v]));

             }

         }

     }

 }

 int main(){

     int t, i, j;

     scanf("%d", &t);

     while(t--){

         scanf("%d", &n);

         for(i = ; i < N; ++i) E[i].clear();

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

             scanf("%s",mp+);

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

                 if(mp[j] == 'Y')

                     E[i].push_back(j);

         }

         dij();

         printf("%d\n", d[n]==inf?-:d[n]);

     }

     return ;

 }

秒客网

51nod 1445 变色DNA(dij)

相关文章