变色DNA（最短路思维题）

个人心得：太水了，还是对最短路不太深入了解，无法构建出最短路模板，然后就是读题能力，

这题的关键在于转换为最短路模板，因为DFS我在24组超时了。

假设把从i到j的代价看做是权值，那么就是对权值的确立了，显而易见，权值跟前面出现的Y的个数有关。

权值建立后就可以用最短路了，特意看了下最短路深入了解了下，每次选择最短的确实可以确定此时的到x的最短路径。

一个话：多思考，多思考

题目：

有一只特别的狼，它在每个夜晚会进行变色，研究发现它可以变成N种颜色之一，将这些颜色标号为0,1,2...N-1。研究发现这只狼的基因中存在一个变色矩阵，记为colormap，如果colormapiijj='Y'则这只狼可以在某一个夜晚从颜色i变成颜色j（一晚不可以变色多次），如果colormapiijj=‘N’则不能在一个晚上从i变成j色。进一步研究发现，这只狼每次变色并不是随机变的，它有一定策略，在每个夜晚，如果它没法改变它的颜色，那么它就不变色，如果存在可改变的颜色，那它变为标号尽可能小的颜色（可以变色时它一定变色，哪怕变完后颜色标号比现在的大）。现在这只狼是颜色0，你想让其变为颜色N-1，你有一项技术可以改变狼的一些基因，具体说你可以花费1的代价，将狼的变色矩阵中的某一个colormapiijj='Y'改变成colormapiijj='N'。问至少花费多少总代价改变狼的基因，让狼按它的变色策略可以从颜色0经过若干天的变色变成颜色N-1。如果一定不能变成N-1，则输出-1.
Input多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=5
每组测试数据有相同的结构构成：
每组数据第一行一个整数N,2<=N<=50。
之后有N行，每行N个字符，表示狼的变色矩阵，矩阵中只有‘Y’与‘N’两种字符，第i行第j列的字符就是colormapiijj。Output每组数据一行输出，即最小代价，无解时输出-1。Sample Input

3

3

NYN

YNY

NNN

8

NNNNNNNY

NNNNYYYY

YNNNNYYN

NNNNNYYY

YYYNNNNN

YNYNYNYN

NYNYNYNY

YYYYYYYN

6

NYYYYN

YNYYYN

YYNYYN

YYYNYN

YYYYNN

YYYYYN

Sample Output

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<vector>

 #include<queue>

 #include<string>

 #include<algorithm>

 using namespace std;

 const int inf=0x3f3f3f3f;

 char mymap[][];

 int book[];

 int s[][];

 int cost[];

 int d[];

 struct node

 {

     int number,dis;

     node(int a,int b)

     {

         number=a,dis=b;

     }

 };

 int sum=inf;

 int t,n;

 vector<int >v[];

 bool operator<(const node& a,const node& b)

 {

     return a.dis<b.dis;

 }

 int solve(){

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

         d[i]=inf;

     memset(book,,sizeof(book));

     priority_queue<node >q;

     q.push(node(,));

     d[]=;

     while(!q.empty()){

         node p=q.top();

         q.pop();

         int x=p.number;

         for(int i=;i<v[x].size();i++)

         {

             int u=v[x][i];

             if(d[u]>d[x]+s[x][u])

             {

                 d[u]=d[x]+s[x][u];

                 q.push(node(u,d[u]));

             }

         }

     }

     return d[n-]==inf?-:d[n-];

 }

 int main(){

     scanf("%d",&t);

     while(t--){

         scanf("%d",&n);

         memset(s,,sizeof(s));

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

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

                 s[i][j]=(i==j)?:inf;

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

            {

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

                int nu=;

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

                {

               if(mymap[i][j]=='Y'){

                 v[i].push_back(j);

               cost[j]=(j==)?:cost[j-]+;

               }

               else

                 cost[j]=(j==)?:cost[j-];

                 s[i][j]=(j==)?:cost[j-];

                }

            }

            cout<<solve()<<endl;

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

             v[i].clear();

     }

     return ;

 }

巴特西

变色DNA（最短路思维题）

最新文章

热门文章