P3315 [SDOI2014]酗酒者【征求spj】

    • 0通过
    • 3提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 2014 山东 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Alice 发现:人在心情不好的时候,便会选择酗酒。这往往与OI 选手比赛胜利后的欢腾庆祝不同,酗酒者喝醉后便会忘记回家的路,然后在大街上无规律地乱走乱逛,同时喊着一些谁也听不懂的话。

    这几天,Bob 因为考试的原因心情很不好,每天晚上都会在城里面找一处酒吧。喝醉后离开酒吧开始在城市街道中无规律乱走,直到某一时刻,若他碰巧遇到了在夜晚出来看星星的Alice,便会被她带回家。

    已知Alice 和Bob 所在的城市街道可以被描绘为一个N 行M 列的格点地图,N 行依次编号为0 到N-1,M 列依次编号为0 到M-1。城市中共有N*M 处路口,每一个路口可以用坐标(i,j)表示。若i<N,则(i,j)与(i+1,j)有无向的连边,边权长度p[i][j],表示走过这一条路所需的时间。若j<M,则(i,j)与(i,j+1)有连无向边,边权长度q[i][j]。

    对于给定的两个点(u,v)和(s,t)分别为Bob 今晚去的酒吧的位置,和Alice 今晚看星星的位置。Bob 离开酒吧后,对于每一个路口,他会等概率选择其中之一,然后走向下一个路口。在走到下一个路口之前,Bob 不会回头。同时Bob 并不会因为之前走过什么道路而影响之后的行走路线。

    具体来说:如果Bob 从(3,4)走到(3,5),他有可能在抵达(3,5)后立刻折回(3,4)。对于四叉路口,Bob 向每一个方向行走的概率都是1/4,对于三叉路口(这只存在于城市的边界上)则是1/3,对于二叉路口(这只存在于城市的4 个角落)就是1/2。

    Alice 希望知道,从Bob 离开酒吧,Alice 期望情况下还需要等多久才能等到Bob,即对于给定的两个点(u,v)与(s,t),Bob 从(u,v)走到(s,t)的期望用时是多少?

    输入输出格式

    输入格式:

    第一行N,M。 之后N-1 行,每行M 个正整数,其中第i 行第j 个为p[i][j]。

    之后N 行,每行M-1 个正整数,其中第i 行第j 个为q[i][j]。 单独一行给出一个整数Q,表示总询问次数。

    之后Q 行,每行有4 个整数u,v,s,t。

    输出格式:

    一共Q 行,每一行对应一次询问:从(u,v)走到(s,t)的期望距离是多少?你的答案可以保 留任意多位小数,但只有与正确答案的错误率在0.1%内才算正确。

    输入输出样例

    输入样例#1: 复制
    2 2
    1 2
    3
    4
    4
    0 0 0 1
    1 0 0 1
    1 1 0 1
    0 1 1 0
    输出样例#1: 复制
    7.0000
    10.0000
    8.0000
    10.0000

    说明

    对于10%的数据,N*M<=25。

    对于30%的数据,N*M<=625。

    对于50%的数据,N*M<=2500。

    对于100%的数据,N*M<=10000,Q<=100。p[][]和q[][]<=200。

    此外存在10%的数据,min{N,M}<=10。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。