Luogu P1875 佳佳的魔法药水

YorkWu

June 1, 2019

1145 views

No comments

331 words

OI 题目

[链接](https://www.luogu.org/problemnew/show/P1875 "链接")

* * *

图论，明显是dijkstra，$d\[i\]$数组保存第$i$个药水的最小配置价格，$cnt\[i\]$保存第$i$个药水最小配置价格的方案数，具体过程： 1. 每次找一个没有访问过的配置价格最小的药水$x$。 2. 枚举所有可以和$x$组成新药水的药水$i$并且已经访问过的节点。 3. 如果$x$和$i$组成的新药水的最小配置价格$d\[j\]<d\[x\]+d\[i\]$，那就更新，并且$cnt\[j\]=cnt\[x\] \\times cnt\[i\]$ 4. 否则如果$d\[j\]=d\[x\]+d\[i\]$，那么$cnt\[j\]+=cnt\[i\] \\times cnt\[x\]$ 代码：
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    
    int n,m;
    int a[1509][1509];
    struct node{
        int x,y;
        bool v;
    }d[1509][1509];
    bool flag=0;
    
    int yc[4]={0,0,-1,1},xc[4]={1,-1,0,0};
    
    void dfs(int x,int y,int rx,int ry){
        if(flag) return;
        if(d[x][y].v&&(d[x][y].x!=rx||d[x][y].y!=ry)){
            flag=1;
            return;
        }
        d[x][y].x=x,d[x][y].y=y,d[x][y].v=1;
        for(int i=0;i<4;i++){
            int nx,ny;
            if(x+xc[i]==0) nx=n;
            else if(x+xc[i]==n+1) nx=1;
            else nx=x+xc[i];
            if(y+yc[i]==0) ny=m;
            else if(y+yc[i]==m+1) ny=1;
            else ny=y+yc[i];
            int nrx=rx+xc[i],nry=ry+yc[i];
            if(!a[nx][ny]&&(d[nx][ny].x!=nrx||d[nx][ny].y!=nry||!d[nx][ny].v)){
                dfs(nx,ny,nrx,nry);
            }
        }
    }
    
    int main(){
        node start;
        while(cin>>n>>m){
            flag=0;
            for(int i=1;i<=n;i++){
                string c;
                cin>>c;
                for(int j=1;j<=m;j++){
                    d[i][j].x=0,d[i][j].y=0,d[i][j].v=0;
                    a[i][j]=0;
                    if(c[j-1]=='#') a[i][j]=1;
                    if(c[j-1]=='S') start.x=i,start.y=j;
                }
            }
            dfs(start.x,start.y,start.x,start.y);
            if(flag) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        return 0;
    }
```

Last modification：March 14, 2020