BZOJ 2143 飞飞侠 最短路

Description

飞飞国是一个传说中的国度，国家的居民叫做飞飞侠。飞飞国是一个N×M的矩形方阵，每个格子代表一个街区。然而飞飞国是没有交通工具的。飞飞侠完全靠地面的弹射装置来移动。每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹射能力。我们设第i行第j列的弹射装置有Aij的费用和Bij的弹射能力。并规定有相邻边的格子间距离是1。那么，任何飞飞侠都只需要在(i,j)支付Aij的费用就可以任意选择弹到距离不超过Bij的位置了。如下图 （从红色街区交费以后可以跳到周围的任意蓝色街区。） 现在的问题很简单。有三个飞飞侠，分别叫做X，Y，Z。现在它们决定聚在一起玩，于是想往其中一人的位置集合。告诉你3个飞飞侠的坐标，求往哪里集合大家需要花的费用总和最低。

Input

输入的第一行包含两个整数N和M，分别表示行数和列数。接下来是2个N×M的自然数矩阵，为Aij和Bij 最后一行六个数，分别代表X，Y，Z所在地的行号和列号。

Output

第一行输出一个字符X、Y或者Z。表示最优集合地点。第二行输出一个整数，表示最小费用。如果无法集合，只输出一行NO

Sample Input

4 4
0 0 0 0
1 2 2 0
0 2 2 1
0 0 0 0
5 5 5 5
5 5 5 5
5 5 5 5
5 5 5 5
2 1 3 4 2 2
Sample Output

Z
15
【范围】

分析：额，今天做这道题时很醚，想了想dij强行建边跑最短路，但算了算空间，发现要RE，于是开始醚了，既然建边不行那就不建边吧，嗯，有道理。于是想刚一波广搜加上各种剪枝水过，结果广搜写着写着。。。就写成了SPFA！于是懒得改了，过了样例就气疗，打算拿20分走人，也没剪枝什么的。然后更醚的是，我跑了40分！于是我看了看单点结果，发现前面有3个点是WA了，而后面竟然跑过了第14个点，于是想不通啊，难道我TLE不是太惨？于是在BZOJ交了一发，发现竟然WA,没有TLE，后来在o2下跑，跑了70分，于是信心大增，加上剪枝各种register，然后跑了85分，只剩那很醚的3个点wa掉了，现在还没有调过。。说了这么半天其实，我想说的是这道题，不用建边，暴力跑DIJorSPFA加上各种剪枝是能过的！至于那些什么云端什么的，知道就好了，反正用处我觉得不是太大。（这么说是不是太naive了）；
附上我的蒟蒻醚代码

# include <iostream>
# include <cstdio>
# include <cmath>
# include <list>
# include <cstring>
# include <map>
# include <ctime>
# include <algorithm>
# include <queue>
using namespace std;
typedef long long ll;
int read(){
    register int f=1,i=0;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {i=(i<<3)+(i<<1)+ch-'0';ch=getchar();}
    return f*i;
}
int buf[1024];
inline void write(long long x){
    if(!x){putchar('0');return ;}
    if(x<0){putchar('-');x=-x;}
    while(x){buf[++buf[0]]=x%10,x/=10;}
    while(buf[0]) putchar(buf[buf[0]--]+48);
    return ;
}
const int N=205;
struct data{
    int x,y;
    data(){}
    data(int x,int y) : x(x),y(y){}
}S[5];
int n,m,a[N][N],b[N][N],f[N][N][4];
bool vis[N][N];
inline void BFS(int t){
    memset(vis,0,sizeof(vis));
    data tmp=data(S[t].x,S[t].y);
    queue<data>q;q.push(tmp);
    f[tmp.x][tmp.y][t]=0;vis[tmp.x][tmp.y]=1;
    register int sg=1e9+7,tg=1e9+7;
    while(!q.empty()){
        data p=q.front();q.pop();
        register int d=a[p.x][p.y];
        if(d==0) continue;
        if((f[p.x][p.y][t]+b[p.x][p.y])>=sg&&(f[p.x][p.y][t]+b[p.x][p.y])>=tg) continue;
        for(register int i=max(1,p.x-d);i<=min(n,p.x+d);++i)
            for(register int j=max(1,p.y-d+abs(i-p.x));j<=min(m,p.y+d-abs(i-p.x));++j){
                if(j<1||j>m||(i==p.x&&j==p.y)) continue;
                f[i][j][t]=min(f[i][j][t],f[p.x][p.y][t]+b[p.x][p.y]);
                for(int e=1;e<=3;++e)
                    if(e!=t&&i==S[e].x&&j==S[e].y)
                        if(e!=3) sg= min(sg,f[i][j][t]);
                        else tg= f[i][j][t];
                if(!vis[i][j]) {q.push(data(i,j));vis[i][j]=true;}
            }
    }
}
inline void PRINTF(int ans,int tmp){
        if(tmp==1){cout<<"X"<<endl;write(ans);return ;}
        if(tmp==2){cout<<"Y"<<endl;write(ans);return ;}
        if(tmp==3){cout<<"Z"<<endl;write(ans);return ;}
}
int main()
{

    n=read(),m=read();
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j) a[i][j]=read();
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j) b[i][j]=read();
    for(int i=1;i<=3;++i) S[i].x=read(),S[i].y=read();
    memset(f,127,sizeof(f));
    for(int i=1;i<=3;++i) BFS(i);
    int ans=1e9+7,tmp=1e9+7;
    for(register int i=1;i<=3;++i){
            register int sum=0;
        for(register int j=1;j<=3;++j)
                    if(i!=j) sum+=f[S[i].x][S[i].y][j];
            if(sum<ans) {ans=sum;}    
        }
        for(register int i=1;i<=3;++i){
            register int sum=0;
        for(register int j=1;j<=3;++j)
                    if(i!=j) sum+=f[S[i].x][S[i].y][j];
            if(sum==ans) {tmp=i;break;}    
        }
        PRINTF(ans,tmp);
}

这里是dalao代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define ll long long
using namespace std;

int getint()
{
    int i=0,f=1;char c;
    for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
    if(c=='-')f=-1,c=getchar();
    for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
    return i*f;
}

const int N=205;
const int fx[5]={0,-1,0,1,0};
const int fy[5]={1,0,-1,0,0};
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m,H,X[4],Y[4];
int a[N][N],b[N][N];
ll dis[N][N][N<<1],D[4][4];
struct node
{
    int d,x,y,h;
    friend inline bool operator >(const node &a,const node &b)
    {
        return a.d>b.d;
    }
};
priority_queue<node,vector<node>,greater<node> >q;

void dijkstra(int S,int T1,int T2)
{
    int x,y,d,h;
    bool bz1=false,bz2=false;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k<=H;k++)
                dis[i][j][k]=INF;
    while(!q.empty())q.pop();
    x=X[S],y=Y[S];
    dis[x][y][a[x][y]]=b[x][y];
    q.push((node){b[x][y],x,y,a[x][y]});
    while(!q.empty())
    {
        x=q.top().x,y=q.top().y,d=q.top().d,h=q.top().h;
        q.pop();
        if(x==X[T1]&&y==Y[T1]&&!h)
            D[S][T1]=d,bz1=true;
        if(x==X[T2]&&y==Y[T2]&&!h)
            D[S][T2]=d,bz2=true;
        if(bz1&&bz2)return;
        if(h>0)
        {
            for(int i=0;i<5;i++)
            {
                int dx=x+fx[i],dy=y+fy[i];
                if(dx<1||dx>n||dy<1||dy>m)continue;
                if(dis[dx][dy][h-1]>d)
                {
                    dis[dx][dy][h-1]=d;
                    q.push((node){d,dx,dy,h-1});
                }
            }
        }
        else
        {
            h=a[x][y];
            if(dis[x][y][h]>d+b[x][y])
            {
                dis[x][y][h]=d+b[x][y];
                q.push((node){dis[x][y][h],x,y,h});
            }
        }
    }
}

int main()
{
    //freopen("friend.in","r",stdin);
    //freopen("friend.out","w",stdout);
    n=getint(),m=getint();
    H=n+m-2;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=min(getint(),H);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            b[i][j]=getint();
    X[1]=getint(),Y[1]=getint();
    X[2]=getint(),Y[2]=getint();
    X[3]=getint(),Y[3]=getint();
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            D[i][j]=INF;
    dijkstra(1,2,3);
    dijkstra(2,1,3);
    dijkstra(3,1,2);
    ll ans=INF;char p;
    if(D[2][1]+D[3][1]<ans)ans=D[2][1]+D[3][1],p='X';
    if(D[1][2]+D[3][2]<ans)ans=D[1][2]+D[3][2],p='Y';
    if(D[1][3]+D[2][3]<ans)ans=D[1][3]+D[2][3],p='Z';
    if(ans==INF)puts("NO");
    else cout<<p<<'\n'<<ans;
    return 0;
}

当然还有dalao用什么线段树，set维护建边，然后玄学跑过的这种，还是自己去研究吧。