最短路的變形，題意比較簡單，具體看代碼
1 /*
2 * SOUR:pku 2353
3 * ALGO:dp
4 * DATE: 2009年 12月 12日 星期六 20:05:20 CST
5 * COMM:3
6 * */
7 #include<iostream>
8 #include<cstdio>
9 #include<cstdlib>
10 #include<cstring>
11 #include<algorithm>
12 #include<queue>
13 using namespace std;
14 typedef long long LL;
15 const int maxint = 0x7fffffff;
16 const long long max64 = 0x7fffffffffffffffll;
17 const int N = 512;
18 const int inf = 100000001;
19 int m,n,x,y;
20 int g[N][N],out[N*N],top,dis[N][N],vis[N][N],pre[N][N][2];
21
22 struct Path
23 {
24 int x,y;
25 int len;
26 Path(){}
27 Path(int a,int b,int c) { x = a,y = b,len = c;}
28 friend bool operator < (Path a,Path b) {
29 return a.len > b.len;
30 }
31 };
32
33 int search()
34 {
35 int i,j,k;
36 for(i = 1;i < m;i++) {
37 for(j = 0;j < n;j++) {
38 dis[i][j] = maxint;
39 }
40 }
41 for(i = 0;i < n;i++) {
42 dis[0][i] = g[0][i];
43 }
44 priority_queue<Path> que;
45 for(i = 0;i < n;i++) {
46 que.push(Path(0,i,g[0][i]));
47 }
48
49 int sum;
50 int res = maxint;
51 while(!que.empty()) {
52 Path u = que.top(); que.pop();
53 if(u.x == m - 1) {
54 if(u.len < res) {
55 res = u.len;
56 x = u.x;
57 y = u.y;
58 continue;
59 }
60 }
61 if(u.len != dis[u.x][u.y])
62 continue;
63
64 if (dis[u.x +1][u.y] > u.len + g[u.x+1][u.y]) {
65 dis[u.x +1][u.y] = u.len + g[u.x+1][u.y];
66 que.push(Path(u.x + 1,u.y,u.len + g[u.x+1][u.y]));
67 pre[u.x+1][u.y][0] = u.x;
68 pre[u.x+1][u.y][1] = u.y;
69 }
70
71 i = u.y - 1;
72 if(i >= 0 && i < n) {
73 sum = g[u.x][i];
74 if (dis[u.x][i] > u.len + sum) {
75 dis[u.x][i] = u.len + sum;
76 que.push(Path(u.x,i,u.len + sum));
77 pre[u.x][i][0] = u.x;
78 pre[u.x][i][1] = u.y;
79 }
80 }
81
82 i = u.y + 1;
83 if(i >= 0 && i < n) {
84 sum = g[u.x][i];
85 if (dis[u.x][i] > u.len + sum) {
86 dis[u.x][i] = u.len + sum;
87 que.push(Path(u.x,i,u.len + sum));
88 pre[u.x][i][0] = u.x;
89 pre[u.x][i][1] = u.y;
90 }
91 }
92 }
93 return sum;
94 }
95
96 int main()
97 {
98 int i,j,k;
99 scanf("%d%d",&m,&n);
100 for(i = 0;i < m;i++) {
101 for(j = 0;j < n;j++) {
102 scanf("%d",&g[i][j]);
103 pre[i][j][0] = -1;
104 pre[i][j][1] = -1;
105 }
106 }
107
108 int res = search();
109 //printf("%d\n",res);
110 int tx,ty;
111 while(x != -1 && y != -1) {
112 out[top++] = y;
113 tx = pre[x][y][0];
114 ty = pre[x][y][1];
115 x = tx,y = ty;
116 }
117 for(i = top - 1;i >= 0;i--) {
118 printf("%d\n",out[i] + 1);
119 }
120 return 0;
121 }
122
123