[codevs2070]爱情之路
试题描述
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，完成多少次考验呢？
输入
第一行为两个整数n，m表示有n个城市，m条双向路。
第2行到第m+1行，每行有3个整数x，y，t和一个字符char，城市x,y之间有路，通过这条路花费的时间为t，这条路的特殊标志为 char。
输出
输出1行，两个整数表示yh到达城市n花费的最少时间和该时间内通过的最多次考验数，如果不能到达则输出’HOLY SHIT!’
输入示例
L
O
V
E
输出示例
数据规模及约定
对于100%数据，1≤n≤1314，0≤M≤13520
题解
设置状态为 (u, t) 表示当前所在节点 u，并且刚刚经过种类为 t 的边，跑最短路。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <queue>
using namespace std; int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
} #define maxn 1324
#define maxm 27050
#define oo (1ll << 60)
#define LL long long
int n, m, head[maxn], next[maxm], to[maxm], dist[maxm], type[maxm]; void AddEdge(int a, int b, int c, int d) {
to[++m] = b; dist[m] = c; type[m] = d; next[m] = head[a]; head[a] = m;
swap(a, b);
to[++m] = b; dist[m] = c; type[m] = d; next[m] = head[a]; head[a] = m;
return ;
} LL d[5][maxn];
int t[5][maxn];
bool vis[5][maxn];
struct Node {
int u, tp, t;
LL d;
Node() {}
Node(int _1, LL _2, int _3, int _4): u(_1), d(_2), tp(_3), t(_4) {}
bool operator < (const Node& T) const { return d != T.d ? d > T.d : t < T.t; }
} ;
priority_queue <Node> Q;
void Dijkstra(int s) {
for(int j = 0; j < 4; j++)
for(int i = 1; i <= n; i++) d[j][i] = oo;
d[4][s] = 0; Q.push(Node(s, 0, 4, 0));
while(!Q.empty()) {
Node u = Q.top(); Q.pop();
if(vis[u.tp][u.u]) continue;
vis[u.tp][u.u] = 1;
// printf("tp: %d, u: %d %lld\n", u.tp, u.u, d[u.tp][u.u]);
for(int e = head[u.u]; e; e = next[e]) if((u.tp < 4 && (u.tp + 1) % 4 == type[e]) || (u.tp == 4 && !type[e])) {
if(d[type[e]][to[e]] > d[u.tp][u.u] + dist[e]) {
d[type[e]][to[e]] = d[u.tp][u.u] + dist[e];
t[type[e]][to[e]] = t[u.tp][u.u] + (type[e] == 3);
if(!vis[type[e]][to[e]]) Q.push(Node(to[e], d[type[e]][to[e]], type[e], t[type[e]][to[e]]));
}
else if(d[type[e]][to[e]] == d[u.tp][u.u] + dist[e] && t[type[e]][to[e]] < t[u.tp][u.u] + (type[e] == 3)) {
t[type[e]][to[e]] = t[u.tp][u.u] + (type[e] == 3);
if(!vis[type[e]][to[e]]) Q.push(Node(to[e], d[type[e]][to[e]], type[e], t[type[e]][to[e]]));
}
}
}
return ;
} int main() {
n = read(); int m = read();
for(int i = 1; i <= m; i++) {
int a = read(), b = read(), c = read(), d;
char tp[2]; scanf("%s", tp);
if(tp[0] == 'L') d = 0;
if(tp[0] == 'O') d = 1;
if(tp[0] == 'V') d = 2;
if(tp[0] == 'E') d = 3;
AddEdge(a, b, c, d);
} Dijkstra(1);
if(vis[3][n]) printf("%lld %d\n", d[3][n], t[3][n]);
else puts("HOLY SHIT!"); return 0;
}
数据有点坑，比如说整张图只有一个点的智障问题。