邮电科技大学

视频题解点击此处查看

题目阅读

​ AC狗送外卖，但是学校的楼梯太堵了，所以每走过一个寝室门口就要花费很多时间。问你AC狗送完外卖所需的最小时间。

题意抽象

​ 给你一幅图，上下层只能通过两侧端点，问你走完指定坐标最小需要多少时间。

算法分析

本题采用前缀和预处理端点再进行迪杰斯特拉最短路进行处理。

由于代码过长，这边讲解关键的思路。

在存图后，将每层所需要的时间进行前缀和进行处理，之后设立每层楼梯口的端点为起始点，进行重写图层。最后进行迪杰斯特拉即可。

代码讲解

#include <cstring>
#include <cstdio>

#define maxr 2000
#define maxs 200
#define inf -1

int r, s, grid[maxr][maxs], sum[maxr][maxs];
int G[maxr][2][3], dp[maxr][2][maxr][2];
void initsum() { 
	for( int i = 0; i < r; ++i ) {
		sum[i][0] = grid[i][0];
		for( int j = 1; j < s; ++j ) sum[i][j] = sum[i][j-1] + grid[i][j]; // 前缀和处理 
	}
}
int fsum( int i, int l, int r ) { 
	if( r == 0 ) return 0;
	if( l == 0 ) return sum[i][r-1];
	return sum[i][r-1] - sum[i][l-1];
}

void load() {
	scanf( "%d%d", &r, &s );
	for( int i = 0; i < r; ++i )
		for( int j = 0; j < s; ++j ) scanf( "%d", &grid[i][j] );
}

void initg() {  
	for( int i = 0; i < r; ++i ) {
		if( i == 0 ) G[i][0][0] = G[i][1][0] = inf;
		else { G[i][0][0] = grid[i-1][0]; G[i][1][0] = grid[i-1][s-1]; }
		
		if( i+1 == r ) G[i][0][2] = G[i][1][2] = inf;
		else { G[i][0][2] = grid[i+1][0]; G[i][1][2] = grid[i+1][s-1]; }
		
		G[i][0][1] = fsum( i, 1, s );
		G[i][1][1] = fsum( i, 0, s-1 );
	}
}

int manji( int a, int b ) {
	if( a == inf ) return b;
	if( b == inf ) return a;
	return a<b? a: b;
}

void initdp() { 
	memset( dp, inf, sizeof dp );
	
	for( int k = 0; k < 2; ++k ) {
		for( int i = 0; i < r; ++i ) {
			dp[i][k][i][k] = 0;
			
			int ll = 0, rr = 0;
			for( int j = i;; ++j) {
				dp[i][k][i][1-k] = manji( dp[i][k][i][1-k], ll+rr+G[j][k][1] );
				if( j+1 == r ) break;
				ll += G[j][k][2];
				rr += G[j+1][1-k][0];
			}
			
			ll = rr = 0;
			for( int j = i;; --j) {
				dp[i][k][i][1-k] = manji( dp[i][k][i][1-k], ll+rr+G[j][k][1] );
				if( j-1 < 0 ) break;
				ll += G[j][k][0];
				rr += G[j-1][1-k][2];
			}
		}
	}
	
	for( int t = 1; t < r; ++t ) {
		
		for( int i = 0; i < r-t; ++i ) {
			for( int k = 0; k < 2; ++k ) {
				dp[i][k][i+t][k] = manji( dp[i][k][i+t][k], dp[i+1][k][i+t][k] + G[i][k][2] );
				dp[i][k][i+t][k] = manji( dp[i][k][i+t][k], dp[i][k][i][1-k] + G[i][1-k][2] + dp[i+1][1-k][i+t][k] );
				
				dp[i][k][i+t][1-k] = manji( dp[i][k][i+t][1-k], G[i][k][2] + dp[i+1][k][i+t][1-k] );
				dp[i][k][i+t][1-k] = manji( dp[i][k][i+t][1-k], dp[i][k][i][1-k] + G[i][1-k][2] + dp[i+1][1-k][i+t][1-k] );
			}
		}
	
		for( int i = t; i < r; ++i ) {
			for( int k = 0; k < 2; ++k ) {
				dp[i][k][i-t][k] = manji( dp[i][k][i-t][k], dp[i-1][k][i-t][k] + G[i][k][0] );
				dp[i][k][i-t][k] = manji( dp[i][k][i-t][k], dp[i][k][i][1-k] + G[i][1-k][0] + dp[i-1][1-k][i-t][k] );
				
				dp[i][k][i-t][1-k] = manji( dp[i][k][i-t][1-k], G[i][k][0] + dp[i-1][k][i-t][1-k] );
				dp[i][k][i-t][1-k] = manji( dp[i][k][i-t][1-k], dp[i][k][i][1-k] + G[i][1-k][0] + dp[i-1][1-k][i-t][1-k] );
			}
		}
		
	}
}

int dist( int r1, int s1, int r2, int s2 ) {
	int d1 = fsum( r1, 0, s1 ) + dp[r1][0][r2][0] + fsum( r2, 1, s2+1 );
	int d2 = fsum( r1, 0, s1 ) + dp[r1][0][r2][1] + fsum( r2, s2, s-1 );
	
	int d3 = fsum( r1, s1+1, s ) + dp[r1][1][r2][0] + fsum( r2, 1, s2+1 );
	int d4 = fsum( r1, s1+1, s ) + dp[r1][1][r2][1] + fsum( r2, s2, s-1 );

	int ret = manji( manji( d1, d2 ), manji( d3, d4 ) );
	if( r1 == r2 ) {
		if( s1 < s2 ) ret = manji( ret, fsum( r1, s1+1, s2+1 ) );
		else ret = manji( ret, fsum( r1, s2, s1 ) );
	}
	
	return ret;
}

void solve() {
	long long sol = grid[0][0];
	int m, a, b, cr = 0, cs = 0;
	for( scanf( "%d", &m ); m; --m ) {
		scanf( "%d%d", &a, &b );
		
		sol += dist( cr, cs, a-1, b-1 );
		
		cr = a-1;
		cs = b-1;
	}
	printf( "%lld\n", sol );
}

int main() {
	load();
	initsum();
	initg();
	initdp();
	solve();
	return 0;
}