题意：
给定n个点m条边的无向图
每次必须沿着LOVE走，到终点时必须是完整的LOVE，且至少走出一个LOVE，
问这样情况下最短路是多少，在一样短情况下最多的LOVE个数是多少。
有自环。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
typedef __int64 ll;
const ll Inf = 4611686018427387904LL;
const int N = 1314 + 100;
const int E = 13520 * 2 + 100;
const int M = N * 4 + 100;
struct Edge {
ll len;
int v, f, nex;
Edge() {
}
Edge(int _v, int _f, ll _len, int _nex) {
v = _v;
f = _f;
len = _len;
nex = _nex;
}
};
struct node{
int to, f;
node(int b=0,int d=0):to(b),f(d){}
};
Edge eg[E];
ll dis[N][4], tim[N][4];
bool vis[N][4];
int T, n, g[N], idx; int re(char c) {
if (c == 'L')
return 0;
else if (c == 'O')
return 1;
else if (c == 'V')
return 2;
else
return 3;
}
void addedge(int u, int v, ll len, int f) {
eg[idx] = Edge(v, f, len, g[u]);
g[u] = idx++;
}
void spfa() {
memset(vis, 0, sizeof vis);
for (int i = 0; i < n; ++i)
for (int j = 0; j < 4; ++j) {
dis[i][j] = Inf;
tim[i][j] = 0;
}
queue<node>q;
q.push(node(0,3));
dis[0][3] = 0;
tim[0][3] = 0;
while(!q.empty()){
node u = q.front(); q.pop(); vis[u.to][u.f] = 0;
for(int i = g[u.to]; ~i; i = eg[i].nex){
int y = eg[i].v, f = eg[i].f;
if(f != (u.f+1)%4)continue;
bool yes = false;
if(dis[y][f] > dis[u.to][u.f]+eg[i].len)
{
dis[y][f] = dis[u.to][u.f]+eg[i].len;
tim[y][f] = tim[u.to][u.f];
if(f == 3)
tim[y][f]++;
yes = true;
}
else if(dis[y][f] == dis[u.to][u.f]+eg[i].len) {
ll tmp = tim[u.to][u.f];
if(f == 3)
tmp++;
if(tmp > tim[y][f])
tim[y][f] = tmp, yes = true;
}
else if(tim[y][f]==0) {
ll tmp = tim[u.to][u.f];
if(f == 3)
tmp++;
if(tmp > tim[y][f])
dis[y][f] = dis[u.to][u.f]+eg[i].len, tim[y][f] = tmp, yes = true;
}
if(yes && vis[y][f] == 0)
vis[y][f] = 1, q.push(node(y, f));
}
}
}
void work() {
int m, u, v; ll len;
char s[5];
memset(g, -1, sizeof g);
idx = 0; scanf("%d %d", &n, &m);
while (m -- > 0) {
scanf("%d%d%I64d%s", &u, &v, &len, s);
-- u; -- v;
addedge(u, v, len, re(s[0]));
addedge(v, u, len, re(s[0]));
}
spfa();
ll ansdis = dis[n - 1][3], ansnum = tim[n - 1][3];
printf("Case %d: ", ++T);
if (ansdis == Inf || ansnum == 0) {
puts("Binbin you disappoint Sangsang again, damn it!");
} else {
printf("Cute Sangsang, Binbin will come with a donkey after travelling %I64d meters and finding %I64d LOVE strings at last.\n", ansdis, ansnum);
}
}
int main() {
int cas;
T = 0;
scanf("%d", &cas);
while (cas -- > 0)
work();
return 0;
}
/*
99
4 4
1 2 1 L
2 4 1 O
4 1 1 V
1 4 1 E 1 4
1 1 1 L
1 1 1 O
1 1 1 V
1 1 1 E 1 0 */