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