题目链接：
http://codeforces.com/contest/677/problem/D
题意：
让你求最短的从start->...->1->...->2->...->3->...->...->p的最短路径。
题解：
这题dp的阶段性还是很明显的，相同的值得方格为同一个阶段，然后求从阶段1->2->3...->p的阶段图最短路。
初始化所有a[x][y]==1的格子为起始点到(x,y)坐标的距离。
方程式为dp[x1][y1]=min(dp[x1][y1],dp[x2][y2]+abs(x2-x1)+abs(y2-y1))，其中a[x1][y1]=a[x2][y2]+1。
但是这要n*n*m*m的复杂度。
x阶段到x+1阶段的转移数为cnt[x]*cnt[x+1]，这个太大，并且多来几个就会爆了，但注意如果cnt[x]*cnt[x+1]大了，其他的如
cnt[x']*cnt[x'+1]就有可能会变小，因为sum(cnt[i])是固定的，
那么根据这个特性，我们可以考虑分块！，当cnt[x]*cnt[x+1]<=m*n的时候直接暴力，如果大了就用最短路（spfa就可以）
这样跑出来的时间复杂度为O(n*m*sqrt(n*m)*log(n*m))，那个log(n*m)是spfa跑出来的。
具体的均摊时间复杂度证明：http://codeforces.com/blog/entry/45181?#comment-297475
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<utility>
#include<vector>
#include<algorithm>
#include<queue>
#define mp make_pair
#define X first
#define Y second
using namespace std; const int maxn = ; int dp[maxn][maxn],mat[maxn][maxn];
int cnt[maxn*maxn],inq[maxn][maxn],d[maxn][maxn];
vector<pair<int,int> > G[maxn*maxn];
int n, m, p; inline int get_dis(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
} const int dx[] = { -,,, };
const int dy[] = { ,,-, }; void init() {
memset(dp, 0x7f, sizeof(dp));
memset(cnt, , sizeof(cnt));
} int main() {
while (scanf("%d%d%d", &n, &m, &p) == && n) {
init();
int xt, yt;
for (int i = ; i < n; i++) {
for (int j = ; j < m; j++) {
scanf("%d", &mat[i][j]);
if (mat[i][j] == ) dp[i][j] = get_dis(,,i,j);
if (mat[i][j] == p) xt = i, yt = j;
cnt[mat[i][j]]++;
G[mat[i][j]].push_back(mp(i, j));
}
}
for (int i = ; i <= p; i++) {
if (cnt[i - ] * cnt[i] <= m*n) {
for (int j = ; j < G[i].size(); j++) {
int x2 = G[i][j].X, y2 = G[i][j].Y;
for (int k = ; k < G[i - ].size(); k++) {
int x1 = G[i - ][k].X, y1 = G[i - ][k].Y;
dp[x2][y2] = min(dp[x2][y2], dp[x1][y1] + get_dis(x1, y1, x2, y2));
}
}
}
else {
memset(d, 0x7f, sizeof(d));
memset(inq, , sizeof(inq));
queue<pair<int, int> > Q;
for (int j = ; j < G[i - ].size(); j++) {
pair<int, int> u = G[i - ][j];
d[u.X][u.Y] = dp[u.X][u.Y], inq[u.X][u.Y] = ;
Q.push(mp(u.X, u.Y));
}
while (!Q.empty()) {
pair<int, int> u = Q.front(); Q.pop();
inq[u.X][u.Y] = ;
if (mat[u.X][u.Y] == i) dp[u.X][u.Y] = min(dp[u.X][u.Y], d[u.X][u.Y]);
for (int j = ; j < ; j++) {
int x = u.X + dx[j], y = u.Y + dy[j];
if (x < || x >= n || y < || y >= m) continue;
if (d[x][y] > d[u.X][u.Y] + ) {
d[x][y] = d[u.X][u.Y] + ;
if (!inq[x][y]) inq[x][y] = , Q.push(mp(x, y));
}
}
}
}
}
printf("%d\n", dp[xt][yt]);
}
return ;
}