校内测试-城堡

 

题目 

 

测试得分：　　100

 

主要算法 ：　　最短路-dijkstra，矩阵动规

 

题干：

　　矩阵中求左上角的点到右下角的点的距离，不能从下往上走

 

分析：

　　方案1（动规）

　　初步判定算法

　　　　对于这题，只能从上往下行走，对于到达每一个点的最优值，一定是从最上方下来的最优值，与左右两边最优值的比较，初步确定算法动态规划

　　分析初步算法

 　　　　对于从两边来的最优值，只有左边目前是一路DP过来的最优值，而对于右边则是一个未知的，所以要进行两步DP，想从左边扫一遍左值，在从右扫一遍右值，上方，左右三者取一个min则是到这个点的最小花

　　方案2（最短路）

　　初步判定算法

　　　　典型的最短路问题

　　分析初步算法　　　　

　　　　将每一个节点，按照从上到下，从左到右的顺序编号，点数为N*M

 　　　　建立到右边一个点，权值为右边那个点的权值的边，再建立到左边一个点，权值为左边那个点的权值的边，再建立到下边一个点，权值为下边那个点的权值的边。边数为3*M*N

　　　　 跑一个最短路dijkstra，时间复杂度O（n*log(m)），对于这道题时间上是跑不过去的，可以得部分分

　　

　代码

#include<queue>
#include<stdio.h>
#include<stdlib.h>
#define INF 2147483647
#define FORa(i,s,e) for(int i=s;i<=e;i++)
#define FORs(i,s,e) for(int i=s;i>=e;i--)
#define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++
#define File(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout);using namespace std;
static char buf[1000000],*pa=buf,*pb=buf;
inline int read();const int M=1000,N=1000;
struct Node{int next,to,dis;
}edge[M*N*4];
bool bz[M*N];
int a[N+1][M+1]; 
int n,m,star,end,dis[M*N],head[M*N],num_edge,fdis[N+1][M+1];
inline int min(int fa,int fb){return fa<fb?fa:fb;}
void Add_edge(int from,int to,int d)
{num_edge++,edge[num_edge]=(Node){head[from],to,d},head[from]=num_edge;
}
struct Que{int u,dis;bool operator < (const Que &q) const{ return dis>q.dis;} 
}q;
priority_queue<Que> que;
void Solve()
{FORa(i,1,n) FORa(j,1,m) a[i][j]=read();FORa(i,1,n) FORa(j,2,m) Add_edge((i-1)*m+j-1,(i-1)*m+j,a[i][j]),Add_edge((i-1)*m+j,(i-1)*m+j-1,a[i][j-1]);FORa(j,1,m) FORa(i,2,n) Add_edge((i-2)*m+j,(i-1)*m+j,a[i][j]);FORa(i,1,m*n) dis[i]=INF;star=1,dis[star]=0,que.push((Que){star,0});while(!que.empty()){q=que.top(),que.pop();if(bz[q.u]) continue;bz[q.u]=1;for(int i=head[q.u];i;i=edge[i].next){if(dis[edge[i].to]>dis[q.u]+edge[i].dis){dis[edge[i].to]=dis[q.u]+edge[i].dis;if(!bz[edge[i].to]) que.push((Que){edge[i].to,dis[edge[i].to]});}}}printf("%d",dis[m*n]);
}
void Solve2()
{FORa(i,1,n) FORa(j,1,m)    a[i][j]=read();FORa(i,1,m)  a[1][i]=a[1][i-1]+a[1][i],fdis[1][i]=a[1][i];FORa(i,2,n){FORa(j,1,m){if(j>1) fdis[i][j]=a[i][j]+min(fdis[i-1][j],fdis[i][j-1]);else fdis[i][j]=a[i][j]+fdis[i-1][j];}FORs(j,m,1){if(j<=m-1) fdis[i][j]=min(fdis[i][j],a[i][j]+min(fdis[i-1][j],fdis[i][j+1]));else fdis[i][j]=min(fdis[i][j],a[i][j]+fdis[i-1][j]);}}printf("%d",fdis[n][m]);
}
int main()
{File("castle");n=read(),m=read();if(n*m<=100) Solve();else Solve2();return 0;
}
inline int read()
{register int x(0);register int f(1);register char c(gc);while(c<'0'||c>'9') f=c=='-'?-1:1,c=gc;while(c>='0'&&c<='9') x=(x<<1)+ (x<<3)+(c^48),c=gc;return x*f;
}