自动搬运

查看原文

来自洛谷，原作者为

	彭程远 手握日月摘星辰，世间无我这般人

搬运于2025-08-24 21:38:58，当前版本为作者最后更新于2020-12-21 12:54:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

为什么像个阅读题？？？

题目描述

其实就是一个最短路，只要你能转化为一个图。

题目分析

把输入的三种方式转为边，然后跑一遍dij即可

代码

#include<bits/stdc++.h>//万能头好评
#define Pair pair<int,pair<int,int> >
#define MAXN 300+10
#define MAXM 90000+10
using namespace std;
struct tu{
	int next,d;
	char n;
	pair<int,int> from,to;//链式前向星
}e[MAXM];
pair<int,int> s,t;
int o,n,m,nu,h[MAXN][MAXN],d[MAXN][MAXN],v[MAXN][MAXN],hm,dh,pr[MAXN][MAXN];//记得二维数组
char ans[MAXN];
void cun(pair<int,int> from1,pair<int,int> to1,int di,char n1){
	e[++nu].next=h[from1.first][from1.second];
	e[nu].to=to1;
	e[nu].n=n1;//标准链式前向星操作（字符也要存）
	e[nu].d=di;
	e[nu].from=from1;
	h[from1.first][from1.second]=nu;
}
void dij(){
	memset(d,0,sizeof(d));
	memset(v,0,sizeof(v));
	priority_queue<Pair,vector<Pair>,greater<Pair> > q;
	for(int i=0;i<=6;i++)
        for(int j=0;j<=m;j++)
    		d[i][j]=2147483647;
	d[s.first][s.second]=0;
	q.push(Pair(d[s.first][s.second],s));
	while(!q.empty()){
		pair<int,int> k=q.top().second;
		q.pop();
		if(v[k.first][k.second])
			continue;
		v[k.first][k.second]=1;
		for(int i=h[k.first][k.second];i;i=e[i].next)
			if(d[k.first][k.second]+e[i].d<=d[e[i].to.first][e[i].to.second]){
				d[e[i].to.first][e[i].to.second]=d[k.first][k.second]+e[i].d;
				pr[e[i].to.first][e[i].to.second]=i;
				q.push(Pair(d[e[i].to.first][e[i].to.second],e[i].to));
			}
	}//堆优dij
}
int main(){
	cin>>s.second>>s.first>>t.second>>t.first>>dh>>hm;
	m=hm/dh;
	s.second/=dh;
	t.second/=dh;
	for(int i=0;i<m;i++)
		for(int j=1;j<=6;j++){
			int x;
			cin>>x;
			pair<int,int> a,b;
			a.first=b.first=j;
			a.second=i;
			b.second=i+1;
			cun(a,b,x,'R');
		}
	for(int i=0;i<=m;i++)
		for(int j=1;j<=5;j++){
			int x;
			cin>>x;
			pair<int,int> a,b;
			a.first=j;
			b.first=j+1;
			a.second=i;
			b.second=i;
			cun(a,b,x,'A');
		}
	for(int i=2;i<=m;i++)
		for(int j=1;j<=5;j++){
			int x;
			cin>>x;
			pair<int,int> a,b;
			a.first=j;
			b.first=j+1;
			a.second=i;
			b.second=i-1;
			cun(a,b,x,'D');
		}//三个（真讨厌）
	dij();
	cout<<d[t.first][t.second]<<endl;
	for(int i=pr[t.first][t.second];i;i=pr[e[i].from.first][e[i].from.second])
		ans[++o]=e[i].n;
	for(int i=o;i;i--)
		cout<<ans[i];
	exit(0);//完美结束
}

AC记录