首页 > 代码库 > 爱情之路
爱情之路
【题目描述】
有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<cstdio>#include<cstring>#include<queue>using namespace std;struct Node{ int T,S,T1,T2;}i[27051]; //两倍。queue <int> 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<dis[T][i[a].T]) //更新最短路。 { if (i[a].T==3) Road[T][3]=Road[t][2]+1; else Road[T][i[a].T]=Road[t][(i[a].T+3)%4]; dis[T][i[a].T]=dis[t][(i[a].T+3)%4]+i[a].S; if (!Vis[T]) { Q.push(T); //入队。 Vis[T]=true;/* 判断负环，但在本题中没有必要。 Sum[T]++; if (Sum[T]>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;}
爱情之路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。