首页 > 代码库 > AC日记——爱情之路 codevs 2070
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 200005using namespace std;struct sp { int t,now;};struct EdgeType { int v,w,e,type;};struct EdgeType edge[maxn<<1];int if_z,n,m,dis[5][maxn],cnt,head[maxn],times[5][maxn],tot;char Cget;bool if_[5][maxn];inline void in(int &now){ now=0,if_z=1,Cget=getchar(); while(Cget>‘9‘||Cget<‘0‘) { if(Cget==‘-‘) if_z=-1; Cget=getchar(); } while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; 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=1; if(Cget==‘O‘) t=2; if(Cget==‘V‘) t=3; if(Cget==‘E‘) t=4; 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,127/3,sizeof(dis)); dis[4][1]=0,if_[4][1]=true; queue<struct sp>que;que.push(node(4,1)); while(!que.empty()) { sp pos=que.front(); if_[pos.t][pos.now]=false;que.pop(); int to=(pos.t%4)+1; 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]+1; 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]+1); if(!if_[to][edge[i].v]) { que.push(node(to,edge[i].v)); if_[to][edge[i].v]=true; } } } if(tot==0) tot++,dis[4][1]=0x7ffffff; } if(dis[4][n]>99999||times[4][n]<4) cout<<"HOLY SHIT!"; else cout<<dis[4][n]<<" "<<times[4][n]/4; cout<<endl; return 0;}
AC日记——爱情之路 codevs 2070
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。