UVA116 单向 DSP（多段图最短路）

单向 DSP

【题目链接】单向 DSP

【题目类型】dp

&题解：

紫书P271 这块的字典序排序我觉得挺厉害的，每次都把那3步sort一下，之后if (v< d[i][j]) 这块的小于号用的很好，因为只有小于才变，而不是小于等于，所以就保证的字典序。

【时间复杂度】O(m*n)

&代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf("%d",&(N))
#define SII(N,M) scanf("%d %d",&(N),&(M))
#define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i--)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<"="<<(x)<<endl;
#define DGG(x,y) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<" "<<#z<<"="<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}
const double EPS = 1e-9 ;
/*  ////////////////////////   C o d i n g  S p a c e   ////////////////////////  */
const int MAXN = 1000 + 9 ;
#define next nnext
int n,m,a[MAXN][MAXN],d[MAXN][MAXN],next[MAXN][MAXN];
void Solve()
{
    while(~SII(m,n)){
        rep(i,m) rep(j,n) SI(a[i][j]);
        int ans=INF,first=0;
        cle(d,0x3f);
        for (int j=n-1;j>=0;j--){
            for (int i=0;i<m;i++){
                if (j==n-1) d[i][j]=a[i][j];
                else {
                    int rows[]={i,i+1,i-1};
                    if (i==0) rows[2]=m-1;
                    if (i==m-1) rows[1]=0;
                    sort(rows,rows+3);
                    for (int k=0;k<3;k++){
                        int v=d[rows[k]][j+1]+a[i][j];
                        if (v<d[i][j]){d[i][j]=v; next[i][j]=rows[k];}
                    }
                }
                if (j==0&&d[i][0]<ans){ans=d[i][0]; first=i;}
            }
        }
        // PIarr(d,m,n)
        // PIarr(next,m,n)
        for (int j=0,i=first;j<n;i=next[i][j],j++)printf("%d%c", i+1,j==n-1?'
':' ');
        PI(ans)
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out","w",stdout);
#endif
//iostream::sync_with_stdio(false);
//cin.tie(0), cout.tie(0);
    // int T;cin>>T;while(T--)
    Solve();
    return 0;
}