来自"NOCOW"

DP，从下向上DP，对于每一层再分别从左到右、从右到左依次更新一遍，注意记录pre

program ural1029;
const
  maxm=100;
  maxn=500;
var
  fee,sum,old,min:array[1..maxn]of longint;
  path:array[2..maxm,1..maxn]of integer;
  m,f:byte;
  n,i,j,finish:integer;
  best:longint;
procedure outpath(f:byte;p:integer); //为什么我用递归输出会爆栈-_-|||
  var
    i:integer;
  begin
    if f=1 then
      writeln(p)
    else begin
      outpath(f-1,path[f,p]);
      if path[f,p]<p then
        for i:=path[f,p] to p do
          writeln(i)
      else
        for i:=path[f,p] downto p do
          writeln(i);
    end;
  end;
begin
  readln(m,n);
  for i:=1 to n do
    read(min[i]);
 
  for f:=2 to m do begin
    old:=min;
    for i:=1 to n do begin
      read(fee[i]);
      min[i]:=maxlongint;
    end;
    sum[1]:=fee[i];
    for i:=2 to n do
      sum[i]:=sum[i-1]+fee[i];
 
    for i:=1 to n do begin
      for j:=i to n do begin
        if old[j]+sum[j]<min[i] then begin
          min[i]:=old[j]+sum[j];
          path[f,i]:=j;
        end;
        if old[i]+sum[j]<min[j] then begin
          min[j]:=old[i]+sum[j];
          path[f,j]:=i;
        end;
      end;
      for j:=i+1 to n do
        dec(sum[j],fee[i]);
    end;
  end;
 
  best:=maxlongint;
  for i:=1 to n do
    if min[i]<best then begin
      best:=min[i];
      finish:=i;
    end;
 
  outpath(m,finish);
end.

---

这题不用DP也能作。。 将每个房间看作节点，再建立一个源点和终点， 然后将能更新的每两个房间之间建立一条边。 这样，问题转化为为从源点s到终点t的最短路径。 只不过权值在节点上，算法是一样的。 此处使用spfa实现，复杂度为O(E),即O(n*m)与DP一样。

#include<iostream>
using namespace std;
int a[100][500];
int q[50001]={0};
bool e[50001]={false};
int d[50001];
int f[50001];
int n,m;
int h=0,t=1;
void relax(int u,int i,int v){
	if(d[u]+v<d[i]){
		d[i]=d[u]+v;
		f[i]=u;
		if(!e[i]){
			e[i]=true;
			q[t]=i;
			if(++t>=50001)t=0;
		}
	}
}
int getindex(int x,int y){return x*m+y;}//y from 0 to m-1,x from 0 to n
int getl(int i){return (i-1)/m;}//from 0 to n-1
int getroom(int i){return (i-1)%m;}//from 0 to m-1
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			cin>>a[i][j];
	for(int i=1;i<=n*m+1;i++)d[i]=1000000000;
	d[0]=0;
	//get minimum on n*m+1
	q[0]=0;e[0]=true;
	while(h!=t){
		int u=q[h];if(++h>=50001)h=0;
		e[u]=false;
		if(u==0){
			for(int i=1;i<=m;i++)
				relax(u,i,a[0][i]);				
		}
		else if(u!=n*m+1){
			if(getroom(u)!=0)relax(u,u-1,a[getl(u)][getroom(u)-1]);//the room  on its left
			if(getroom(u)!=m-1)relax(u,u+1,a[getl(u)][getroom(u)+1]);//the room on its right
			if(getl(u)!=n-1)relax(u,u+m,a[getl(u)+1][getroom(u)]);//the room above it
			else relax(u,n*m+1,0);
		}		
		cout<<"ok: "<<u<<endl;
	}	
	for(int i=f[n*m+1];i!=0;i=f[i])cout<<getroom(i)<<' ';
	cout<<endl;
}