【题目描述】

有n(n <= 1314)个城市和m(m <= 13520)条双向公路，每条公路连接着一个或两个城市，通过一条公路需要耗费时间，且每条公路均有一个特定标识“L”、“O”、“V”、“E”。

小Y从1号城市出发，需要前往n号城市，他必须按照“L” --> “O” --> “V” --> “E” --> “L” --> “O” --> “V” --> “E” --> ······的顺序选择公路，且其所走的第一条公路为“L”，最后一条公路为“E”，每走完一个完整的“LOVE”就算通过了一次考验。

现询问小Y耗费的最少时间是多少，以及在该时间内最多能够通过多少次考验。

【输入描述】

第一行输入两个整数n、m，表示城市数目和公路数目；

接下来m行，每行输入三个整数X、Y、T和一个字符，表示城市X、Y之间存在一条公路，通过这条公路需耗费时间T，及其特殊标志。

【输出描述】

输出两个整数，分别表示耗费最少的时间，以及在该时间内能够通过的最多的考验次数，如果不能到达n号城市，输出“HOLY SHIT!”。

【样例输入】

样例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

【样例输出】

样例1：

4 1

 

样例2：

HOLY SHIT!

源代码：#include
       
        #include
        
         #include
         
          using namespace std;struct Node{    int T,S,T1,T2;}i[27051]; //两倍。queue 
          
            Q; int n,m,Head[1315],Next[13521],dis[1315][4],Road[1315][4];bool Vis[1315]={
     0};void SPFA() //SPFA快忘掉了。{    memset(dis,0x3f,sizeof(dis)); //dis[i][j]表示走到节点i，且后续字母编号应为j的最短路数值。    Q.push(1);    Vis[1]=true; //是否在队列之中。    dis[1][3]=0;    bool Flag(0);    while (!Q.empty())    {        int t=Q.front();        Q.pop();        Vis[t]=false;        for (int a=Head[t];a;a=Next[a]) //遍历此点的边。        {            int T=i[a].T2;            if (dis[t][(i[a].T+3)%4]==0x3f) //字母不符条件。              continue;            if (dis[t][(i[a].T+3)%4]+i[a].S==dis[T][i[a].T]) //最短路数值相等。            {                if (i[a].T==3)                  Road[T][3]=max(Road[t][2]+1,Road[T][3]); //Road[i][j]表示走到节点i，且此节点字母编号为j的最多考验数值。                else                  Road[T][i[a].T]=max(Road[T][i[a].T],Road[t][(i[a].T+3)%4]);            }            if (dis[t][(i[a].T+3)%4]+i[a].S
           
            n) //入队的次数大于节点总数，肯定就是陷入死循环了。                      return;*/                }            }        }        if (n==1&&!Flag) //自环，因为前面已经把dis[1][3]赋值为0，暴力判断并修改一次即可。        {            Flag=true;            dis[1][3]=0x3f;        }    }}void Init() //类似于边表，只不过边表是按Num++序，但此数据结构直接跳到了边数之外。{    for (int a=1;a<=m;a++)    {        char t;        scanf("%d%d%d",&i[a].T1,&i[a].T2,&i[a].S);        scanf(" %c",&t); //新字符读入方式get√。        if (t=='L')          i[a].T=0;        if (t=='O')          i[a].T=1;        if (t=='V')          i[a].T=2;        if (t=='E')          i[a].T=3;        Next[a]=Head[i[a].T1]; //Next[]存储的是此节点的上一条边的编号。        Head[i[a].T1]=a; //Head[]存储的是该条边的编号，为下一条边的处理做准备。        i[a+m].T1=i[a].T2; //无向边就是两条有向边。        i[a+m].T2=i[a].T1;        i[a+m].S=i[a].S;        i[a+m].T=i[a].T;        Next[a+m]=Head[i[a+m].T1]; //同理于上。        Head[i[a+m].T1]=a+m;    }}int main() //这道题目叙述有意思啊。{    scanf("%d%d",&n,&m);    Init();    SPFA();    if (dis[n][3]==0x3f) //无法得出答案。      printf("HOLY SHIT!");    else      printf("%d %d",dis[n][3],Road[n][3]);    return 0;}