题目描述 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<<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; }