标签:SPFA

REPORT HIHOCODER1354-积水的城市

REPORT HIHOCODER1354-积水的城市

SPFA
本来想是做一个图然后把积水点相连的路径删掉然后发现这样做好蠢
这个程序的C#代码我写得很难看……贴http://blog.csdn.net/piaocoder/article/details/52173939的代码吧

#include <iostream>
#include <set> 
#include <queue>
#include <cstring>
  
#define INF 0x3f3f3f3f  
using namespace std;  
  
const int N = 505;  
const int M = 505;  
const int dx[] = {-1,0,1,0};  
const int dy[] = {0,1,0,-1};  
  
struct node{  
    int x,y,d;  
    node(int a,int b,int c) : x(a),y(b),d(c){}  
    bool operator < (const node &s) const{  
        return d > s.d;  
    }  
};  
  
int n,m;  
int A[M];  
int B[N];  
int vis[N][M];  
set<pair<int, int> > dead;  
  
int solve(int x,int y,int p,int q){  
    priority_queue<node> pq;  
    pq.push(node(x,y,0));  
    vis[x][y] = 0;  
    while(!pq.empty()){  
        node cur = pq.top();  
        pq.pop();   
        for(int i = 0; i < 4; ++i) {  
            int xx = cur.x + dx[i];  
            int yy = cur.y + dy[i];  
            if(xx <= 0 || yy <= 0 || xx > n || yy > m || dead.find(make_pair(xx, yy)) != dead.end())  
                continue;  
            int d = dx[i] == 0 ? cur.d + A[min(cur.y, yy)]:cur.d + B[min(cur.x, xx)];  
            if (vis[xx][yy] <= d)  
                continue;  
            if (xx != p || yy != q)  
                pq.push(node(xx, yy, d));  
            vis[xx][yy] = d;  
        }//
    }  
    return vis[p][q] == INF?-1:vis[p][q];  
}  
  
int main(){  
    while(~scanf("%d%d",&n,&m)){  
        for(int i = 1; i < n; ++i)  
            scanf("%d",&B[i]);  
        for(int i = 1; i < m; ++i)  
            scanf("%d",&A[i]);  
        int k;  
        scanf("%d",&k);  
        for(int i = 0; i < k; ++i){  
            int x, y;  
            scanf("%d%d",&x,&y);  
            dead.insert(make_pair(x, y));  
        }  
        int Q;  
        scanf("%d",&Q);  
        for(int i = 0; i < Q; ++i){  
            int x,y,p,q;  
            scanf("%d%d%d%d",&x,&y,&p,&q);  
            memset(vis,INF,sizeof(vis));  
            printf("%d\n",solve(x,y,p,q));  
        }  
    }  
    return 0;  
}