java学习视频 android开发实战 Appuim环境搭建 JavaWeb Nginx环境搭建 Java Spring knockoutjs gdb vue原理 bootstrap后台模版 it教学视频 nginx教程视频 python转16进制 华为路由器ipv6配置 ie内核浏览器怎么设置 mysql设置自增初始值 js获取body的高度 linux管道符 linux查找文件内容 mysql教程 python环境搭建 python测试 python文件操作 java在线学习 java变量 java集合框架 java删除 java定义字符串 linux装机 房产证生成器 Ext2Fsd phpqrcode iphone滚动截屏 kmservice 怎么设置迅雷为默认下载器 js分页 spss22安装教程 ps怎么画漫画 凯立德下载 黑暗系情侣头像
当前位置: 首页 > 学习教程  > 编程学习

COGS 201. [BYVoid S1] 埃雷萨拉斯的宝藏

2021/1/9 2:01:39 文章标签: 托尔达戈怎么去

★★ 输入文件:eldrethalas.in 输出文件:eldrethalas.out 简单对比时间限制:1 s 内存限制:256 MB 问题描述 一万两千年前,精灵还是在艾萨拉女王的统治下,辛德拉是女王手 下一名很有地位的法师。他受…

★★   输入文件:eldrethalas.in   输出文件:eldrethalas.out   简单对比
时间限制:1 s   内存限制:256 MB

问题描述

一万两千年前,精灵还是在艾萨拉女王的统治下,辛德拉是女王手 下一名很有地位的法师。他受任建造了一座城市,来保存女王的法师们进行魔法研究的成果和法术物品。这个城市就是埃雷萨拉斯。永恒之井的爆炸,使这里的精灵 和总部联系中断,并失去了永恒之井的水做为能量的来源。辛德拉的后人为了满足魔法的欲望,捕猎了一个恶魔,伊莫塔尔,并以水晶塔建造了一个带有能量平衡系 统的结界监狱,水晶塔从恶魔身上吸取能量,一部分维持结界监狱,一部分可以让精灵狂热者吸收。近万年平安无事。但是现在,恶魔的能量被消耗得越来越多,最 终变得不稳定,已经难以维持结界监狱的消耗。统治这里的托尔塞林王子开始下令屠杀。只有少数狂热者之外的其他人都要死,以减少魔法能量的消耗。

 

终于,强大的戈多克食人魔入侵了埃雷萨拉斯,并杀死了大量的精灵。他们把这里当作他们的领地,叫做厄运之槌。面临灭顶之灾的精灵们把他们祖先留下的宝藏用魔法结界藏了起来,以防戈多克食人魔抢走。

 

作为一名勇敢的探险者,你悄悄来到了埃雷萨拉斯,来寻找传说中的宝藏。终于,你看到了宝藏,他就在你的前方不远处。但是你不能贸然前进,因为路上有着强大的魔法结界。这些结界根据能量的不同分为P种,踏入每种结界,你都会受到一定的伤害。为了拿到宝藏,这些伤害算不了什么。但是你要尽可能地减少伤害,请你设计一条路线,使你穿越结界获取宝藏受到的伤害最少。

 

下面是一个魔法结界能量示意图,结界是一个正方形,内部有P种不同的能量,每种字母表示一种能量。你从最上端开始走,每次能走到与你所在的位置邻接的一个单元格,或者在同种能量结界中任意传送。重复进入同一种能量结界不会再次受到伤害。

 

|AAABBC|

|ABCCCC|

|AABBDD|

|EEEEEF|

|EGGEFF|

|GGFFFF|

 

你有H点生命值,请你在贸然行动之前先判断是否能够活着(生命值大于0)穿越结界拿到宝藏,如果能够,请求出最大的生命值。

 

输入格式

第1行 三个非负整数 N P H。N为结界的边长,P为不同的能量结界的数量,H为你的生命值。

第2-P+1行 每行一个非负整数,表示走到该种能量结界受到的伤害值。

第P+2至第P+2+N行 每行N个正整数,为地图上该单元格的能量种类的编号,编号为1..P。

 

输出格式

如果你能够穿越结界到达对岸的宝藏,输出最多剩余的生命值。如果不能穿越,输出NO。

 

样例输入

6 7 10

3

1

2

2

1

1

3

1 1 1 2 2 3

1 2 3 3 3 3

1 1 2 2 4 4

5 5 5 5 5 6

5 7 7 5 6 6

7 7 6 6 6 6

 

样例输出

7

 

样例说明

路线为

起始-2-5-6-目标

1 1 1 2 2 3

1 2 3 3 3 3

1 1 2 2 4 4

5 5 5 5 5 6

5 7 7 5 6 6

7 7 6 6 6 6

 

数据规模

对于40%数据

4<=N<=10

 

对于100%数据

4<=N<=50

1<=P<=N*N

0<=H<=200000000

 

 

最短路

Rank1(窃喜)

平板电视快的飞起。。

屠龙宝刀点击就送

#include <iostream>
#include <cstdio>
#include <ext/pb_ds/priority_queue.hpp>
#define N 500000
#define pa pair<int,int>
using namespace std;
using namespace __gnu_pbds;
bool vis[N];
int n,p,h,cnt,fx[5]={1,-1,0,0},fy[5]={0,0,-1,1},mp[55][55],harm[2505],to[N<<1],far[N],val[N<<1],head[N<<1],nextt[N<<1];
typedef __gnu_pbds::priority_queue<pa,greater<pa>,pairing_heap_tag>heap;
heap::point_iterator id[N];
inline void ins(int u,int v,int w)
{
    nextt[++cnt]=head[u];to[cnt]=v;val[cnt]=w;head[u]=cnt;
}
void dijkstra()
{
    heap q;
    for(int i=0;i<=n*n+1;++i) vis[i]=false,far[i]=0x3f3f3f3f;
    far[0]=0;
    id[0]=q.push(make_pair(0,0));
    for(int u;!q.empty();)
    {
        u=q.top().second;q.pop();
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=head[u];i;i=nextt[i])
        {
            int v=to[i];
            if(far[v]>far[u]+val[i])
            {
                far[v]=far[u]+val[i];
                val[i]=0;
                if(id[v]!=0) q.modify(id[v],make_pair(far[v],v));
                else id[v]=q.push(make_pair(far[v],v));
            }
        }
    }
}
int Main()
{
    freopen("eldrethalas.in","r",stdin);
    freopen("eldrethalas.out","w",stdout);
    scanf("%d%d%d",&n,&p,&h);
    for(int i=1;i<=p;++i) scanf("%d",&harm[i]);
    for(int i=1;i<=n;++i)
     for(int j=1;j<=n;++j)
      scanf("%d",&mp[i][j]);
    for(int a=1;a<=n;++a)
     for(int b=1;b<=n;++b)
      for(int c=1;c<=n;++c)
       for(int d=1;d<=n;++d)
        if(mp[a][b]==mp[c][d]&&a!=c&&b!=d) ins((a-1)*n+b,(c-1)*n+d,0);
    for(int i=1;i<=n;++i)
     for(int j=1;j<=n;++j)
      for(int k=0;k<4;++k)
      {
          int ti=i+fx[k],tj=j+fy[k];
          if(ti<1||ti>n||tj<1||tj>n||mp[i][j]==mp[ti][tj]) continue;
          ins((i-1)*n+j,(ti-1)*n+tj,harm[mp[ti][tj]]);
      }
    for(int i=1;i<=n;++i) ins(0,i,harm[mp[1][i]]),ins(i,0,harm[mp[1][i]]);
    for(int i=(n-1)*n+1;i<=n*n;++i) ins(i,n*n+1,0),ins(n*n+1,i,0);
    dijkstra();
    if(far[n*n+1]!=0x3f3f3f3f&&h-far[n*n+1]>0) printf("%d\n",h-far[n*n+1]);
    else puts("NO");
    return 0;
}
int sb=Main();
int main(int argc,char *argv[]){;}

 

转载于:https://www.cnblogs.com/ruojisun/p/7710909.html


本文链接: http://www.dtmao.cc/news_show_1100210.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?