AC日记——爱情之路 codevs 2070

2070 爱情之路

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题解

题目描述 Description

yh非常想念他的女朋友小y，于是他决定前往小y所在的那块大陆。

小y所在的大陆共有n个城市，m条双向路，每条路连接一个或两个城市。经过一条路ei需要耗费时间ti。此外，每条路均有一个特定标识，为’L’,’O’,’V’,’E’，中的某个字母。yh从1号城市出发，前往位于n号城市的小y所在处。

为了考验yh，小y规定，yh必须按照‘L’->’O’->’V’->’E’->’L’->’O’->’V’->’E’->.... 的顺序选择路，且所走的第一条路是’L’,最后一条路是’E’，每走完一个完整的’LOVE’算是通过一次考验

在不违背小y要求的前提下，yh想花费最少的时间到达小y的所在地，同在此时间内完成最多次考验。你能帮yh算出，他最少要花多久到达城市n，完成多少次考验呢？

输入描述 Input Description

第一行为两个整数n，m表示有n个城市，m条双向路。

第2行到第m+1行，每行有3个整数x，y，t和一个字符char，城市x,y之间有路，通过这条路花费的时间为t，这条路的特殊标志为 char。

输出描述 Output Description

输出1行，两个整数表示yh到达城市n花费的最少时间和该时间内通过的最多次考验数，如果不能到达则输出’HOLY SHIT!’

样例输入 Sample Input

【样例输入1】

4 4

1 2 1 L

2 1 1 O

1 3 1 V

3 4 1 E

【样例输入2】

4 4

1 2 1 L

2 3 1 O

3 4 1 V

4 1 1 E

样例输出 Sample Output

【样例输出1】

4 1

【样例输出2】

HOLY SHIT!

数据范围及提示 Data Size & Hint

对于100%数据，1≤n≤1314，0≤M≤13520

思路：

　　spfa最短路；

　　每个点都拆成4个状态；

来，上代码：

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define maxn 20005

#define maxm 200005

using namespace std;

struct sp {

    int t,now;

};

struct EdgeType {

    int v,w,e,type;

};

struct EdgeType edge[maxn<<];

int if_z,n,m,dis[][maxn],cnt,head[maxn],times[][maxn],tot;

char Cget;

bool if_[][maxn];

inline void in(int &now)

{

    now=,if_z=,Cget=getchar();

    while(Cget>''||Cget<'')

    {

        if(Cget=='-') if_z=-;

        Cget=getchar();

    }

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

    now*=if_z;

    return ;

}

struct sp node(int t,int now)

{

    sp pos_;

    pos_.t=t,pos_.now=now;

    return pos_;

}

int main()

{

    in(n),in(m);

    int u,v,w,t;

    while(m--)

    {

        in(u),in(v),in(w);cin>>Cget;

        if(Cget=='L') t=;

        if(Cget=='O') t=;

        if(Cget=='V') t=;

        if(Cget=='E') t=;

        edge[++cnt].v=v,edge[cnt].e=head[u],edge[cnt].w=w,edge[cnt].type=t,head[u]=cnt;

        edge[++cnt].v=u,edge[cnt].e=head[v],edge[cnt].w=w,edge[cnt].type=t,head[v]=cnt;

    }

    memset(dis,/,sizeof(dis));

    dis[][]=,if_[][]=true;

    queue<struct sp>que;que.push(node(,));

    while(!que.empty())

    {

        sp pos=que.front();

        if_[pos.t][pos.now]=false;que.pop();

        int to=(pos.t%)+;

        for(int i=head[pos.now];i;i=edge[i].e)

        {

            if(edge[i].type==to&&edge[i].w+dis[pos.t][pos.now]<dis[to][edge[i].v])

            {

                dis[to][edge[i].v]=dis[pos.t][pos.now]+edge[i].w;

//                if(to==4) times[edge[i].v]=max(times[edge[i].v],times[pos.now]+1);

//                if(to==4) times[to][edge[i].v]=max(times[to][edge[i].v],times[pos.t][pos.now]+1);

                times[to][edge[i].v]=times[pos.t][pos.now]+;

                if(!if_[to][edge[i].v])

                {

                    que.push(node(to,edge[i].v));

                    if_[to][edge[i].v]=true;

                }

            }

            else if(edge[i].type==to&&edge[i].w+dis[pos.t][pos.now]==dis[to][edge[i].v])

            {

                times[to][edge[i].v]=max(times[to][edge[i].v],times[pos.t][pos.now]+);

                if(!if_[to][edge[i].v])

                {

                    que.push(node(to,edge[i].v));

                    if_[to][edge[i].v]=true;

                }

            }

        }

        if(tot==) tot++,dis[][]=0x7ffffff;

    }

    if(dis[][n]>||times[][n]<) cout<<"HOLY SHIT!";

    else cout<<dis[][n]<<" "<<times[][n]/;

    cout<<endl;

    return ;

}

巴特西

AC日记——爱情之路 codevs 2070

2070 爱情之路

最新文章

热门文章