题解 P2551 【[AHOI2001]华夏60战斗机】
为什么像个阅读题？？？
题目描述
其实就是一个最短路，只要你能转化为一个图。
题目分析
把输入的三种方式转为边，然后跑一遍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);//完美结束
}