COJ 0244 HDNOIP201404最短路径

HDNOIP201404最短路径

难度级别： A；编程语言：不限；运行时间限制：1000ms；运行空间限制：51200KB；代码长度限制：2000000B

试题描述

a、b、c是3个互不相等的1位正数，用它们和数字0可以填满一个n行n列的方格阵列，每格中都有4种数码中的一个。填入0的格子表示障碍物，不能属于任何路径。你是否能找出一条从1行1列出发，到达n行n列且代价最小的路径呢？注意：每一格只能走向与之相邻的上、下、左、右的非0且不出界的格子。而所谓路径代价指的是路径经过的所有格子中的数字总和。请你编程求出从1行1列的位置出发到达n行n列的最小路径代价，若无法到达就输出-1。

输入

第一行输入数字n。
接下来的n行每行是一个长度为n的数字串，这n个字符串就构成了一个数字符的方阵。方阵中除了'0'外，最多还可以包含3种数字符。

输出

仅有最小代价或-1这一个整数。

输入示例

【输入样例1】
4
1231
2003
1002
1113
【输入样例2】
4
3150
1153
3311
0530

输出示例

【输出样例1】
10
【输出样例2】
-1

其他说明

60%的数据，n<10，80%的数据，n<100，100%的数据，n<1000

题解：好题呀。

一看题就知道普通的最短路不行，那么就要注意到题目的特殊条件：边权是基本确定的。

然后就变成一眼题了：用dij的f递增的思想，窝萌维护几个单调队列就行了。然后就只是O(n^2)的辣。

单调队列的题真是优美啦啦啦~

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<cstring>

 #define PAU putchar(' ')

 #define ENT putchar('\n')

 using namespace std;

 const int maxn=+,inf=-1u>>,u[]={-,,,},v[]={,,-,};

 struct par{int x,y;par(int _x=,int _y=){x=_x;y=_y;}};

 inline int read(){

     int x=,sig=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}

     while(isdigit(ch)) x=*x+ch-'',ch=getchar();

     return x*=sig;

 }

 inline void write(int x){

     if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;

     int len=,buf[];while(x) buf[len++]=x%,x/=;

     for(int i=len-;i>=;i--) putchar(buf[i]+'');return;

 }

 queue<par>q[];char a[maxn][maxn];int n,z,b[],f[maxn][maxn];

 int minq(){

     int r=;

     if(!q[].empty()) r=;

     if(!q[].empty()&&f[q[].front().x][q[].front().y]<f[q[r].front().x][q[r].front().y]) r=;

     if(!q[].empty()&&f[q[].front().x][q[].front().y]<f[q[r].front().x][q[r].front().y]) r=;

     return r;

 }

 void init(){

     memset(f,-,sizeof(f));n=read();

     for(int i=;i<=n;i++)scanf("%s",a[i]+);

     if(a[][]==''||a[n][n]==''){write(-);return;}

     q[].push(par(,));f[][]=inf;

     b[a[][]-'']=++z;

     q[].push(par(,));f[][]=a[][]-'';

     while(f[n][n]<&&!(q[].empty()&&q[].empty()&&q[].empty())){

         int k=minq(),x=q[k].front().x,y=q[k].front().y;q[k].pop();

         for(int d=;d<;d++){

             int i=x+u[d],j=y+v[d];

             if(a[i][j]>''&&f[i][j]<){

                 int c=a[i][j]-'';

                 if(!b[c]) b[c]=++z;

                 k=b[c];

                 q[k].push(par(i,j));

                 f[i][j]=f[x][y]+c;

             }

         }

     }write(f[n][n]);

     return;

 }

 void work(){

     return;

 }

 void print(){

     return;

 }

 int main(){init();work();print();return ;}

巴特西

COJ 0244 HDNOIP201404最短路径

最新文章

热门文章