| 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
|
确实是一道好题。
1000*1000的最短路可能有些吃力，实测卡时1000s+。那么怎么做呢？
方阵中除了'0'外，最多还可以包含3种数字符。
这提醒我们，可以在这上面做些文章。考虑为什么用Heap来优化Dijkstra，是因为有些边很长有些边很短，对于所有入边相同的点，易得它们的距离是递增的。
算法就水落石出了，用3个单调队列代替Heap，注意每次如何取队头和如何加入队尾。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
char A[maxn][maxn];
int n,d[maxn][maxn],vis[maxn][maxn],idx[maxn],tp;
struct Point {
int x,y;
bool operator < (const Point& ths) {return d[x][y]<d[ths.x][ths.y];}
};
queue<Point> q[];
int getfront() {
int c=-;
if(q[].size()) c=;
if(q[].size()&&(c<||q[].front()<q[c].front())) c=;
if(q[].size()&&(c<||q[].front()<q[c].front())) c=;
return c;
}
int mx[]={,-,,},my[]={,,,-};
int solve() {
if(A[][]==''||A[n][n]=='') return -;
q[idx[A[][]]].push((Point){,});d[][]=A[][]-'';
while(q[].size()+q[].size()+q[].size()) {
int t=getfront();int x=q[t].front().x,y=q[t].front().y;q[t].pop();
if(x==n&&y==n) return d[x][y];
if(vis[x][y]) continue;vis[x][y]=;
rep(dir,,) {
int nx=x+mx[dir],ny=y+my[dir];
if(nx>=&&nx<=n&&ny>=&&ny<=n&&A[nx][ny]!=''&&d[x][y]+A[nx][ny]-''<d[nx][ny]) {
d[nx][ny]=d[x][y]+A[nx][ny]-'';
q[idx[A[nx][ny]]].push((Point){nx,ny});
}
}
}
return -;
}
int main() {
n=read();
rep(i,,n) scanf("%s",A[i]+);
memset(idx,-,sizeof(idx));
rep(i,,n) rep(j,,n) {
if(idx[A[i][j]]<&&A[i][j]!='') idx[A[i][j]]=tp++;
d[i][j]=<<;
}
printf("%d\n",solve());
return ;
}