题意：
给定n个点m条边的无向图
每次必须沿着LOVE走，到终点时必须是完整的LOVE，且至少走出一个LOVE，
问这样情况下最短路是多少，在一样短情况下最多的LOVE个数是多少。
有自环。
#include#include #include #include #include #include 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 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;}/*994 41 2 1 L2 4 1 O4 1 1 V1 4 1 E1 41 1 1 L1 1 1 O1 1 1 V1 1 1 E1 0*/