题目背景

NOIP2018 原创模拟题 T2

NOIP DAY1 T2 or DAY2 T2 难度

题目背景改编自小说《哈利波特与密室》。

说明：#4，bug经修复，感谢：@唐子川

题目描述

密室被打开了。

哈利与罗恩进入了密室，他们发现密室由n个小室组成，所有小室编号分别为：1,2,...,n。所有小室之间有m条通道，对任意两个不同小室最多只有一条通道连接，而每通过一条通道都需要Ci 的时间。

开始时哈利与罗恩都在编号为1的小室里，他们的目标是拯救金妮和寻找日记，但是他们发现金妮和日记可能在两个不同的小室里，为了尽快发现真相，他们决定以最少的时间到达两个目标小室。但是某些小室只有会与蛇对话的人才能进入，也就是只有哈利一个人可以进入。

现在，哈利告诉你密室的结构，请你计算他们到达两个目标小室的最短时间。

输入输出格式

输入格式：

第一行 n,m,k 表示有n个小室m条通道，k间小室只有哈利可以进入。

第二行 k 个数，表示只有哈利可以进入的小室的编号。（若k=0，不包含该行）

接下来m行，每行3个数：a,b,c 表示a小室与b小室之间有一条需要花费c时间的通道。

最后一行，两个数 x,y 表示哈利与罗恩需要去的小室的编号

输出格式：

一行，输出一个数，表示到达两个密室的最短时间。

输入输出样例

6 8 1

5

1 2 3

2 3 2

1 3 4

3 4 1

4 6 5

5 6 2

1 6 6

1 5 3

4 6

5

10 13 3

3 4 10

1 2 1

2 3 2

3 4 3

4 5 4

5 6 5

6 7 10

7 8 5

8 9 10

9 10 3

10 1 2

1 9 6

3 8 10

4 6 3

6 8

16

说明

样例解释：

样例一：

哈利：1->5->6 花费时间为5

罗恩：1->3->4 花费时间为5

所以最短时间为5

样例二：

如图，橙色表示目标小室，绿色只有哈利可以通过

哈利：1->2->3->4->6 花费时间为9

罗恩：1->9->8 花费时间为16

所以最短时间为16

数据范围：

10% 数据满足：n<=5

30% 数据满足：n<=20

50% 数据满足：n<=1000

70% 数据满足：n<=10000

100%数据满足：n<=50000 ; a,b,k<=n c<=1000 ;m<=100000，保证罗恩可以在密室1

特殊约定：

30%数据满足：k=0

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 50010

using namespace std;

int snack[MAXN];

int n,m,k,t1,t2,tot1,tot2,bns;

int vis1[MAXN],dis1[MAXN],vis2[MAXN],dis2[MAXN];

int to1[MAXN*],cap1[MAXN*],net1[MAXN*],head1[MAXN];

int to2[MAXN*],cap2[MAXN*],net2[MAXN*],head2[MAXN];

void add1(int u,int v,int w){

    to1[++tot1]=v;cap1[tot1]=w;net1[tot1]=head1[u];head1[u]=tot1;

}

void add2(int u,int v,int w){

    to2[++tot2]=v;cap2[tot2]=w;net2[tot2]=head2[u];head2[u]=tot2;

}

void spfa1(int s){

    queue<int>que1;

    memset(vis1,,sizeof(vis1));

    memset(dis1,0x7f,sizeof(dis1));

    while(!que1.empty())    que1.pop();

    que1.push(s);vis1[s]=;dis1[s]=;

    while(!que1.empty()){

        int now=que1.front();

        que1.pop();vis1[now]=;

        for(int i=head1[now];i;i=net1[i]){

            if(dis1[to1[i]]>dis1[now]+cap1[i]){

                dis1[to1[i]]=dis1[now]+cap1[i];

                if(!vis1[to1[i]]){

                    vis1[to1[i]]=;

                    que1.push(to1[i]);

                }

            }

        }

    }

}

void spfa2(int s){

    queue<int>que2;

    memset(vis2,,sizeof(vis2));

    memset(dis2,0x7f,sizeof(dis2));

    while(!que2.empty())    que2.pop();

    que2.push(s);vis2[s]=;dis2[s]=;

    while(!que2.empty()){

        int now=que2.front();

        que2.pop();vis2[now]=;

        for(int i=head2[now];i;i=net2[i])

            if(dis2[to2[i]]>dis2[now]+cap2[i]){

                dis2[to2[i]]=dis2[now]+cap2[i];

                if(!vis2[to2[i]]){

                    vis2[to2[i]]=;

                    que2.push(to2[i]);

                }

            }

    }

}

void workbns(){

    spfa1(t1);int route=dis1[t2];spfa1();

    bns=min(dis1[t1]+route,min(dis1[t2]+route,min(dis1[t1]*+dis1[t2],dis1[t2]*+dis1[t1])));

}

/*

求图上一点到另外两点的路程和最短？

思路1：求最短路生成树，然后lca求解 (不会写。。。)

思路2: 记录路径，搞一下相同的路径。

思路3：在我快写完思路2的代码时，猛然发现其实不用这样，只要求出s点到其中一点A的最短路，

       然后求A点到另一个点B的最短路，两者之和就可能是答案之一，再求s点到B点的最短路，

       加上A,B两点的最短路，和就是答案之一，然后两个答案比较，取较小的一个，即为答案。

*/

int main(){

    scanf("%d%d%d",&n,&m,&k);

    for(int i=;i<=k;i++){

        int a;scanf("%d",&a);

        snack[a]=;

    }

    for(int i=;i<=m;i++){

        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        if(snack[u]==||snack[v]==){

            add1(u,v,w);add1(v,u,w);

        }

        else {

            add1(u,v,w);add1(v,u,w);

            add2(u,v,w);add2(v,u,w);

        }

    }

    scanf("%d%d",&t1,&t2);

    spfa2();workbns();

    spfa1();

    if(dis2[t1]==&&dis2[t2]==){

        cout<<bns;

        return ;

    }

    else if(dis2[t1]==&&dis2[t2]<){

        spfa1();

        int ans=max(dis2[t2],dis1[t1]);

        ans=min(ans,bns);

        cout<<ans<<endl;

        return ;

    }

    else if(dis2[t2]==&&dis2[t1]<){

        spfa1();

        int ans=max(dis2[t1],dis1[t2]);

        ans=min(ans,bns);

        cout<<ans<<endl;

        return ;

    }

    else{

        spfa1();

        int ans=max(dis1[t1],dis2[t2]);

        ans=min(ans,max(dis1[t2],dis2[t1]));

        ans=min(ans,bns);

        cout<<ans<<endl;

        return ;

    }

}

题目背景

NOIP2018原创模拟题 T3

NOIP DAY1 T3 or DAY 2 T2 难度

贪吃蛇大家都玩过吧，当然不同版本有不同规则。下面介绍PION贪吃蛇。

注意：测试点#4错误已修改，感谢：@EnTaroTassadar

题目描述

表示方法：

该题中贪吃蛇存在于一个n行m列的矩形中，用 ‘.’ 表示空地，用 '#’ 表示蛇身，用 ‘@’表示蛇头，用‘&’表示食物 例如：图一表示5*6的矩形，有一条蛇，蛇长度为7，有两个食物

基本规则：

1.蛇头每一秒就会移动一格，身体自然会跟着移动，用W表示向上，S表示向下，A表示向左，D表示向右

2.蛇每吃一个食物就长度就会加一，而增加的长度体现在食物所在的地方，你可以把吃食物理解成食物变成了蛇头，之前的蛇头变成了蛇身，这一秒不移动

例如：图二的三幅图展示了第一秒，第二秒，和第三秒的情况

3.蛇如果死亡，身体（包括头）一定会全部变成食物

4.PION贪吃蛇的蛇头碰到自己或别的蛇的身体就会死亡

例如：图三的三幅图展示了第二条蛇撞在别人身体上死亡的过程

5.蛇头撞在边界上也会引起死亡，但蛇头刚好现在边界上不会

例如：图四第二幅图虽然蛇头在边界上，但是只是刚好，如果此时进行D操作蛇就会死亡，如果进行W或S就不会

6.如果有操作使蛇头向相反方向运动，之后如果与身体重合蛇也会死亡（比如：图二第一幅图使用A操作,蛇就会死亡，此时在原地成为三个食物，你也可以理解为蛇下一秒不行动而自杀了）

7.两条蛇蛇头相撞，主动撞上的死亡

8.蛇的移动按编号由小到大进行（编号的含义见下文）

输入输出格式

输入格式：

第一行两个数n,m，k表示n*m的矩形，k表示操作次数

接下来n行每行m个字符，表示地图

再接下来c行（注意：图中有几条蛇就有几行），每行k个字符，表示有k个操作（如果执行了某个操作蛇死了，就忽略后面的操作）

我们将蛇编号：按每条蛇蛇头的坐标从小到大编号为1，2，...，c（越靠近上边的坐标越小，如果相同越靠近左边的坐标越小）

例如：图三第一幅图两条蛇的蛇头坐标分别为（4,3），（3,7）所以较长的蛇编号为2，较短的蛇编号为1

输出格式：

c+1行，输出k次操作后每一条蛇的长度，编号；每一行第一个为长度，第二个数为编号

最后一行输出剩下食物的总个数

注意：输出按长度由大到小排序（长度相同按编号由小到大排序），死亡的蛇长度为0

输入输出样例

5 7 6

.&...&.

..##@..

.&...&.

..##@..

.&...&.

DWAAAA

WDDDDD

5 1

0 2

7

9 9 4

.........

.#######.

.......#.

.@#.&@.#.

&.#.&&.#.

&&######.

.&.......

..@####..

.........

ASSD

ASDD

WASD

22 1

4 2

0 3

6

说明

样例说明：

图五，图六展示了从第0秒开始之后每一秒地图的状态，请看图理解（样例二图四有点小错误）

数据范围：

10%数据满足n,m<=5,c=1,k<=3

30%数据满足n,m<=10,c<=2,k<=5

50%数据满足n,m<=50,c<=5,k<=20

70%数据满足n,m<=100,c<=7,k<=50

100%数据满足，n,m<=200,c<=20,k<=100，且图中的蛇不会引起混淆

输入保证图中没有蛇会像这样难以判断：

.#.

##@

#.#

@##

期望 0   实际 0
题目太恶心了，就没写。。。(好吧。。。其实是我懒，那暴力分应该还是可以的)