文档章节

Codevs 2070 爱情之路

机智的帝江
 机智的帝江
发布于 2016/10/30 09:59
字数 1039
阅读 19
收藏 0

题目描述 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 4
1 1 L
1 1 O
1 1 V
1 1 E

贴代码(吐槽一下csdn代码颜色真丑)

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

using namespace std;
const int INF = 2147483647;
const int maxn = 25000;

int n,m;
int dis[maxn][5],s[maxn];
bool vis[maxn];
int first[maxn],next[maxn];
int road[maxn][5];

struct node{
       int u;
       int v;
       int t;
       int b;
}p[maxn];

void spfa()
{
     int i,x,y,k;
     queue <int> q;
     for (i=1;i<=n;i++) dis[i][0]=dis[i][1]=dis[i][2]=dis[i][3]=INF;
     memset (vis,0,sizeof(vis));
     memset (s,0,sizeof(s));
     memset (road,0,sizeof(road));
     q.push(1);
     vis[1]=1;
     dis[1][3]=0;
     int flag=0;
     while (!q.empty())
     {
           x=q.front();
           q.pop();
           vis[x]=0;
           for (k=first[x];k!=0;k=next[k])
           {
               y=p[k].v;
               if (dis[x][(p[k].b+3)%4]==INF) continue;
               if (dis[x][(p[k].b+3)%4]+p[k].t==dis[y][p[k].b])
               {
                 if (p[k].b==3) road[y][3]=max(road[x][2]+1,road[y][3]);
                 else road[y][p[k].b]=max(road[y][p[k].b],road[x][(p[k].b+3)%4]);
               }
               if (dis[x][(p[k].b+3)%4]+p[k].t<dis[y][p[k].b])
               {
                 if (p[k].b==3) road[y][3]=road[x][2]+1;
                 else road[y][p[k].b]=road[x][(p[k].b+3)%4];
                 dis[y][p[k].b]=dis[x][(p[k].b+3)%4]+p[k].t;
                  if (!vis[y])
                  {
                    q.push(y);
                    vis[y]=1;
                  }
               }
           }
     if (n==1&&!flag) {flag=1;dis[1][3]=INF;}         
    }
    return;
}

int main()
{
    scanf("%d%d",&n,&m);
    int i;
    char c;
    memset (first,0,sizeof(first));
    memset (next,0,sizeof(next));
    for (i=1;i<=m;i++)
    {
    scanf ("%d%d%d",&p[i].u,&p[i].v,&p[i].t);
    scanf (" %c",&c);
    if (c=='L') p[i].b=0;
    if (c=='O') p[i].b=1;
    if (c=='V') p[i].b=2;
    if (c=='E') p[i].b=3;
    next[i]=first[p[i].u];
    first[p[i].u]=i;
    p[i+m].u=p[i].v;
    p[i+m].v=p[i].u;
    p[i+m].t=p[i].t;
    p[i+m].b=p[i].b;
    next[i+m]=first[p[i+m].u];
    first[p[i+m].u]=i+m;
    }
    spfa();
    if (dis[n][3]==INF) printf ("HOLY SHIT!");
    else printf ("%d %d",dis[n][3],road[n][3]);
    return 0;
}

本文转载自:http://blog.csdn.net/loi__dijiang/article/details/52794815

机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
《大话西游》里他好像条狗想表达什么?

他好像条狗 看过大话西游的朋友们,剧末有句台词,夕阳武士和紫霞站在城头,至尊宝飞上去,替夕阳武士亲了紫霞,向紫霞告白,夕阳武士说:“他好像条狗”,这句话是想表达什么呢? 当至尊宝离...

产品经理的技术课堂
2018/06/28
0
0
英伟达新利剑:发布RTX20系列新显卡,图灵框架铺垫

     大数据文摘出品   编译:蒋宝尚、CoolBoy   英伟达在2018科隆国际游戏展宣布,新款高端显卡GeForce RTX 2070,RTX 2080和RTX 2080 Ti正式问世。   这些RTX20系列显卡会接替英...

大数据文摘
2018/08/21
0
0
splay的各种操作与简易讲解

基本操作 插入 和二叉查找树一样,但是插入完成后要splay一下(即伸展),伸展操作下面有 伸展 查找前驱或后驱 例题:codevs1285/洛谷P2286/bzoj1208 宠物收养所 删除和合并 先把要删除的点s...

litble
2017/07/07
0
0
业界 | 英伟达新利剑:发布RTX20系列新显卡,图灵框架铺垫

英伟达在2018科隆国际游戏展宣布,新款高端显卡GeForce RTX 2070,RTX 2080和RTX 2080 Ti正式问世。 这些RTX20系列显卡会接替英伟达目前的顶级GPU,包括GeForce GTX 1070,GTX 1080和GTX 108...

技术小能手
2018/08/21
0
0
nginx-1.2.9 已发布

nginx 1.2.9 维护版本发布了,该版本修复了 1.1.4 中存在的一个信息泄漏的安全漏洞 (CVE-2013-2070). 下载地址: nginx-1.2.9 nginx/Windows-1.2.9...

netnova
2013/05/14
2.7K
0

没有更多内容

加载失败,请刷新页面

加载更多

家庭作业——苗钰婷

2 编写一个程序,发出一声警报,然后打印下面的文本: Startled by the sudden sound, Sally shouted, "By the Great Pumpkin, what was that! #include<stdio.h>int main(){......

OSC_Okruuv
24分钟前
4
0
经典系统设计面试题解析:如何设计TinyURL(一)

原文链接: https://www.educative.io/courses/grokking-the-system-design-interview/m2ygV4E81AR 编者注:本文以一道经典的系统设计面试题:《如何设计TinyURL》的参考答案和解析为例,帮助...

APEMESH
25分钟前
3
0
2.面向对象设计原则(7条)

开闭原则 开闭原则的含义是:当应用的需求改变时,在不修改软件实体的源代码或者二进制代码的前提下,可以扩展模块的功能,使其满足新的需求。 实现方法 可以通过“抽象约束、封装变化”来实...

Eappo_Geng
27分钟前
6
0
8086汇编基础 debug P命令 一步完成loop循环

    IDE : Masm for Windows 集成实验环境 2015     OS : Windows 10 x64 typesetting : Markdown    blog : my.oschina.net/zhichengjiu    gitee : gitee.com/zhichengjiu   ......

志成就
32分钟前
3
0
使用nodeJS实现前端项目自动化之项目构建和文件合并

本文转载于:专业的前端网站➜使用nodeJS实现前端项目自动化之项目构建和文件合并 前面的话   一般地,我们使用构建工具来完成项目的自动化操作。本文主要介绍如何使用nodeJS来实现简单的项...

前端老手
45分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部