这道题 我没看出来 他只可以往下走，我看到的 8-connected ；所以今天写一下如果是 8-connected 怎么解；
其实说白了这个就是从上到下走一条线到达最后一行的距离最小； 从Map【a】【b】 到Map【a】【b+1】 的距离是Map【a】【b+1】 以此类推：建图即可；
然后在加一个点0，和n+m+1 点这样在建立一下从 0 点到第一行的边，和最后一行到（n+m+1） 的边 求一个从0 到(n+m+1) 的最短路径就好了，
怎么维护最右侧?： Dijkstra 有 队列优化！多以我们可以再这个由下级队列里面 吧col 号也设置进去；这样就可以使答案的字典序最大，也就是最右侧：
代码.cpp
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <string>
using namespace std;
int n,m;
int mat[105][105];
int dd[][2]={-1,1, -1,0, -1,-1, 0,1, 0,-1, 1,1, 1,0, 1,-1 };
int ddd[][2]={1,-1,1,0,1,1};
bool jude(int x,int y)
{
return x>=1&&x<=n&&y>=1&&y<=m;
}
int ID(int x,int y)
{
return (x-1)*m+y;
}
const int INF = 1000000000;
const int maxn =10000+10;
struct Edge {
int from, to, dist,col;
Edge(){}
Edge(int from,int to,int dist,int col):from(from),to(to),dist(dist),col(col){}
};
struct HeapNode {
int d, u , col;
HeapNode(){}
HeapNode(int d,int u,int col):d(d),u(u),col(col){}
bool operator < (const HeapNode& rhs) const {
if(d==rhs.d) return col<rhs.col;
return d > rhs.d;
}
}; struct Dijkstra {
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
bool done[maxn];
int d[maxn];
int p[maxn];
void init(int n) {
this->n = n;
for(int i = 0; i < n; i++) G[i].clear();
edges.clear();
}
void AddEdge(int from, int to, int dist,int col) {
edges.push_back(Edge(from, to, dist,col));
m = edges.size();
G[from].push_back(m-1);
}
void dijkstra(int s) {
priority_queue<HeapNode> Q;
for(int i = 0; i < n; i++) d[i] = INF;
d[s] = 0;
memset(done, 0, sizeof(done));
Q.push( HeapNode(0, s , 0)) ;
while(!Q.empty()) {
HeapNode x = Q.top(); Q.pop();
int u = x.u;
if(done[u]) continue;
done[u] = true;
for(int i = 0; i < G[u].size(); i++) {
Edge& e = edges[G[u][i]];
if(d[e.to] > d[u] + e.dist) {
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
Q.push(HeapNode(d[e.to], e.to, e.col));
}
}
}
}
void GetShortestPaths(int s, int & dist, vector<int>&paths) {
dijkstra(s);
for(int i = n-1; i <n; i++) {
dist = d[i];
paths.clear();
int t = i;
paths.push_back(t);
while(t != s) {
paths.push_back(edges[p[t]].col);
t = edges[p[t]].from;
}
reverse(paths.begin(), paths.end());
}
}
};
Dijkstra solver;
vector <int> path;
int main()
{
int t,ca=1;
scanf("%d",&t);
while(t--)
{ scanf("%d%d",&n,&m);
solver.init(n*m+2);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&mat[i][j]);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
{
for(int k=0;k<3;k++)
{
int x=i+ddd[k][0];
int y=j+ddd[k][1];
if(!jude(x,y)) continue;
solver.AddEdge(ID(i,j),ID(x,y),mat[x][y],y);
}
// 上边有个dd 数组 （用dd数组 8-connected 然后K 变成上届8 就可以了 ）
}
for(int i=1;i<=m;i++) solver.AddEdge(0,ID(1,i),mat[1][i],i);
for(int i=1;i<=m;i++) solver.AddEdge(ID(n,i),n*m+1,0,105);
int dis=0;
solver.GetShortestPaths(0,dis,path);
printf("Case %d\n",ca++);
for(int i=0;i<path.size()-2;i++)
{
if(i==0) printf("%d",path[i]);
else printf(" %d",path[i]);
}
puts("");
}
return 0;
}