hiho185_alwaysRememberrr的博客-程序员秘密

技术标签: 数据结构&算法  

题目1 : 积水的城市
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
如下图所示,某市市区由M条南北向的大街和N条东西向的道路组成。其中由北向南第i条路和第i+1条路之间的距离是Bi (1 <= i < N),由西向东第i条街和第i+1条街之间的距离是Ai (1 <= i < M)。

这里写图片描述

小Ho现在位于第x条路和第y条街的交叉口,他的目的地是第p条路和第q条街的交叉口。由于连日降雨,城市中有K个交叉口积水太深不能通行。小Ho想知道到达目的地的最短路径的长度是多少。

输入
第一行包含两个整数N和M。(1 <= N, M <= 500)

第二行包含N-1个整数, B1, B2, B3, … BN-1。(1 <= Bi <= 100)

第三行包含M-1个整数, A1, A2, A3, … AM-1。(1 <= Ai <= 100)

第四行包含一个整数K,表示积水的交叉口的数目。 (0 <= K <= 30)

以下K行每行包含2个整数,X和Y,表示第X条路和第Y条街的交叉口积水。(1 <= X <= N, 1 <= Y <= M)

第K+5行包含一个整数Q,表示询问的数目。 (1 <= Q <= 10)

以下Q行每行包含4个整数x, y, p, q,表示小Ho的起止点。起止点保证不在积水的交叉口处。 (1 <= x, p <= N, 1 <= y, q <= M)

输出
对于每组询问,输出最短路的长度。如果小Ho不能到达目的地,输出-1。

样例输入
4 5
2 4 1
3 3 3 2
3
1 3
2 3
3 2
1
1 2 2 4
样例输出
24

思路:直接把交叉点的二维坐标映射成一维的点,因为矩阵边长最大值是500所以最多一共有250000个顶点,大约4*250000=1000000条边,这是很稀疏的图,而且邻接矩阵也存不下,于是用邻接表,求最短路套spfa的模板,建图的比较恶心。

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int M = 10000005;
const int INF = 999999999;
struct node
{
    int u;
    int v;
    int c;

}p[M];

int Next[M];
int  head[M];
long long dist[M];
bool visit[M];
int  now[M];

int  e,top;
int  a,b;
int n,m,k,x,y,Q,p0,q0;

void addnode(int  a,int  b,int c)
{
    p[e].c = c;
    p[e].u = a;
    p[e].v = b;
    Next[e] = head[a];
    head[a] = e++;

}

void init()
{
    memset(head,-1,sizeof(head));
    memset(Next,-1,sizeof(Next));
    e = 0;

}

bool relax(int  u,int  v,int c)
{
    if(dist[v]> dist[u]+c){
        dist[v] = dist[u] + c;
        return true;
    }
    return false;
}

void spfa(int  t)
{   int  j,i;
    int num = n*m;
    memset(visit,0,sizeof(visit));
    for(i=0;i<num;i++){
        dist[i] = INF;
    }
    dist[t] = 0;
    visit[t] = true;
    queue <int>Q;
    Q.push(t);
    while(!Q.empty()){
        int pre = Q.front();
        Q.pop();
        visit[pre] = false;
        for(int i = head[pre];i+1;i=Next[i] ){
            if(relax(pre,p[i].v,p[i].c)&&!visit[p[i].v]){
                Q.push(p[i].v);
                visit[p[i].v] = true;
            }
        }
    }
}
int G[505][505];

int dir[4][2] = {
   {
   0,1},{-1,0},{
   1,0},{
   0,-1}};

int main()
{

    int A[505];
    int B[505];
    cin>>n>>m;

    int num = n*m;

    for(int i = 1; i < n; ++i)
        cin>>B[i];

    for (int i = 1; i < m; ++i)
        cin>>A[i];

    for (int i = 0; i < n ; ++i)
        for (int j = 0; j < m ; ++j)
            G[i][j] = 0;
    init();

    cin>>k;
    for (int i = 0; i < k; ++i){
        cin>>x>>y;
        G[x-1][y-1] = -1;
    }
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            if(G[i][j]!= -1 ){
            if( i < n-1 && j < m-1 ){
                if(G[i][j+1]!=-1){
                addnode(i*m+j,i*m+j+1,A[j+1]);
                addnode(i*m+j+1,i*m+j,A[j+1]);
                }
                if(G[i+1][j]!=-1){
                addnode(i*m+j,(i+1)*m+j,B[i+1]);
                addnode((i+1)*m+j,i*m+j,B[i+1]);
                }
            }
            if(j == m-1 && i <= n-2){
                addnode(i*m+j,(i+1)*m+j,B[i+1]);
                addnode((i+1)*m+j,i*m+j,B[i+1]);
            }
            if(i == n-1 && j <= m-2){
                addnode(i*m+j,i*m+j+1,A[j+1]);
                addnode(i*m+j+1,i*m+j,A[j+1]);
            }
            }
            else{
                for(int k = 0; k < 4; ++k){
                    int dx = i + dir[k][0];
                    int dy = j + dir[k][1];
                    if(dx >=0 && dx < n && dy >=0 && dy < m){
                        addnode(i*m+j,dx*m+dy,INF);
                        addnode(dx*m+dy,i*m+j,INF);

                    }
                }
            }
        }
    }

    cin>>Q;
    while(Q--){
    cin>>x>>y>>p0>>q0;
    int u = (x-1)*m + y-1;
    int v  = (p0-1)*m + q0-1;
    spfa(u);
    if(dist[v]<INF)
        cout<<dist[v]<<endl;
    else
        cout <<"-1"<<endl;

    }
    return 0;
}
上面的代码不知道什么原因一直只有90分,后来看了一下别人的用优先队列优化的BFS觉得代码比较简单,于是学习一波
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

const int M = 550+5;
const int INF =  100000;

int n,m,k,q;
int a[M],b[M],G[M][M],vis[M][M];
int dir[4][2] = {
   {-1,0},{
   1,0},{
   0,-1},{
   0,1}};



int dis(int x,int y,int i)
{
    if( i == 0) return a[x-1];
    if( i == 1) return a[x];
    if( i == 2) return b[y-1];
    return b[y];
}

typedef struct node
{
    int x,y,d;
    node(){}
    node(int u,int v,int c) : x(u),y(v),d(c){}
    node go(int i){
       return node(x+dir[i][0],y+dir[i][1],d+dis(x,y,i));
    }

    bool operator < (const node &s) const{
        return d > s.d;
    }

    bool isok(){

        return x>=1&&x<=n&&y>=1&&y<=m&&!vis[x][y];
    }
};

int main()
{

    cin>>n>>m;

    for(int i = 1; i < n; ++i)
        cin>>a[i];
    for(int i = 1; i < m; ++i)
        cin>>b[i];

    cin>>k;
    for(int i = 1; i <= k; ++i){
        int x,y;
        cin>>x>>y;
        vis[x][y] = 1;
    }
    cin>>q;
    while(q--){
        fill(G[0], G[550] + 550, INF);
        int x, y, s, t;
        cin >> x >> y >> s >> t;
        G[x][y] = 0;
        node start(x,y,0);
        priority_queue<node>que;
        que.push(start);
        while(!que.empty()){
            node now = que.top();
            que.pop();
            for (int i = 0; i < 4; ++i){
                node tmp = now.go(i);
                if(tmp.isok()){
                    if(G[tmp.x][tmp.y] > G[now.x][now.y] + dis(now.x,now.y,i)){
                        G[tmp.x][tmp.y] = G[now.x][now.y] + dis(now.x,now.y,i);
                        que.push(tmp);
                    }
                }
            }
        }
        if(G[s][t]!=INF) cout <<G[s][t]<<endl;
        else
            cout<<"-1"<<endl;
    }

    return 0;
}





版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u014046022/article/details/79079417

智能推荐

pc 与 android webrtc 通信的研究_iteye_4426的博客-程序员秘密

webrtc 的 Android 和 桌面通信的问题,似乎不是我想象的那样,它的数据格式不同。(linux 版本的webrtc 和 Android 版本的,似乎不太一样)所以他的通信方式有以下几种 1.服务器解析RTP 包,然后把对应的视频流,发送给ffmpeg进行解析 2.在服务器上解析android 的 WebRTC的代码。让它能够正常运行。 3.绕道chrome ,...

[babel-plugin-component] If you are using bothon-demand and importing all, make sure to invoke the i..._weixin_30662849的博客-程序员秘密

https://juejin.im/post/5ba314c16fb9a05d0d2868f5转载于:https://www.cnblogs.com/dianzan/p/11383230.html

RHEL 7.0 64位使用CentOS7 yum源_frealn的博客-程序员秘密

Red Hat Enterprise Linux Server(RHEL) 使用CentOS7 yum源安装软件

世安杯-LSB隐写-png_lsb png_「已注销」的博客-程序员秘密

原题是这样的,给了一张图片:皮卡丘。一开始不知道怎么做,就一直在那里纠结。后面知道提示:lsb隐写,弱密码,结合在网上找到的一个介绍,就知道这其实有多简单了。好吧,接下来就介绍一下整个过程吧,我写的是最最具体的,不用你去思考下一步跟上一步是什么关系,照着做就可以做出来,至于如何理解大家就上网找资料咯。首先拿到一张图: 先分析一下: 对于LSB隐写,可使用Stegsolve辅助分析

MySql中 delimiter_mysql中delimiter_墨着染霜华的博客-程序员秘密

delimiter 常应用在存储过程 函数中,默认情况下,delimiter “;” 用于向 MySQL 提交查询语句。在存储过程中每个 SQL 语句的结尾都有个 “;”,如果这时候,每逢 “;” 就向 MySQL 提交的话,那么执行到";“就结束了。DELIMITER 定好结束符为”$$", 按块去执行语句,然后最后再定义回";"。示例:DELIMITER $$drop procedure if exists AddColumnUnlessExists $$create procedure Add

java二叉树生成器,JAVA之二叉树源码_裙主的博客-程序员秘密

brnNodebrnNodebrnNodebrnNodebrnNodebrnNodebrnNodebrnNodebrnNodeclass brnNode&gt;{//定义根结点,初始化为空结点TNode root;//定义结点数量,初始化为 0private int size = 0;//前序遍历public void preIterator(TNode node){if (node != nul...

随便推点

android 中 setContentView() 的前世今生_android setcontentview之前是什么_gaohongijj的博客-程序员秘密

新建一个android项目时,  初始化activity时,总能看到到setContentView(R.layout.main);这行代码,以前只知道这行代码能把main布局文件的内容布局加载并显示出来,但是加载的过程并不是十分清楚,今天经过查询资料,对他的实现过程总结一下,自己学习的同时也希望能帮助有相同疑惑的同仁们。android的编写与java有着莫大的渊源,我们从java一路走来,习惯

16天天天天天天_咸粽的博客-程序员秘密

1:设栈S和队列Q的初始状态为空,元素ABCDEF依次进栈S,出栈后立即进入队列Q,若6个元素出列的顺序为CDBFEA,则栈S的容量至少为(A)A:3B:4C:6D:2解析:出队顺序为CDBFEA则进队顺序为CDBFEA,则出栈顺序为CDBFEA,则在栈中A进B进C进C出D进D出B出E进F进F出E出A出,则最大容量为32:中序周游(遍历)平衡的二叉排序树,可得到最后排序的关键码序列。(...

对比度_澍yeah的博客-程序员秘密

转载地址  http://blog.csdn.net/u012590570/article/details/50346325对比度和线性变换关于什么是对比度这事,不好用一个很明确很严谨的词来概括清楚。对比度高,画面看上去就很硬朗,对比度低,画面看上去就朦朦胧胧,比如下面这张图:对比度和颜色没有关系,换句话说如果使用YUV颜色空间的话,那对比度只与Y通道值(亮度)有关。所以在这里,就...

elementUI 表格组件(包含过滤和排序)----自定义表头_form表头 过滤 ui_有蝉的博客-程序员秘密

父组件HTML&lt;template&gt;&lt;div&gt; &lt;subTable ref="subTableInParent" :tableRules="tableRules" @current-change="onCurrentChange" @selection-change="onSelectionChange" @on-query="refreshTable"&g...

扁平风轮播图大屏展示html页面源码_html图片展示源码-程序员秘密

本源码编码:10156,需要的朋友,点击文末链接后,搜索10156,即可获取。

python代码覆盖工具Coverage.py_coverage cannot be imported to this environment. i_zm_21的博客-程序员秘密

Coverage.pyCoverage.py is a tool for measuring code coverage of Python programs. It monitors your program, noting which parts of the code have been executed, then analyzes the source to identify

推荐文章

热门文章

相关标签