As long as Binbin loves Sangsang
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 753 Accepted Submission(s): 195

Problem Description
Binbin misses Sangsang so much. He wants to meet with Sangsang as soon as possible.
Now Binbin downloads a map from ELGOOG.There are N (1<=N<=1,314) cities in the map and these cities are connected by M(0<=M<=13,520) bi-direct roads. Each road has a length L (1<=L<=1,314,520)and is marked using a unique ID, which is a letter fromthe string LOVE! Binbin rides a DONKEY, the donkey is so strange that it has to walk in the following sequence L->O->V->E->L->O->V->E->…. etc.
Can you tell Binbin how far the donkey has to walk in order to meet with Sangsang?
WARNING: Sangsang will feel unhappy if Binbin ride the donkey without a completeLOVE string.
Binbin is at node 1 and Sangsang is at node N.

Input
The first line has an integer T(1<=T<=520), indicate how many test cases bellow. Each test case begins with two integers N, M (N cities marked using an integer from 1N and M roads). Then following M lines, each line has four variablesU V L letter, means that there is a road between city U,V(1<=U,V<=N) with length L and the letter marked isL,O,V or E Output For each test case, output a string 1. Case ?: Binbin you disappoint Sangsang again, damn it! If Binbin failed to meet with Sangsang or the donkey cant finish a path withthe full LOVE string. 2. Case ?: Cute Sangsang, Binbin will come with a donkey after travelling ? meters and finding ? LOVE strings at last. Of cause, the travel distance should be as short as possible, and at the same time the LOVE string should be as long as possible. Sample Input 2 4 4 1 2 1 L 2 1 1 O 1 3 1 V 3 4 1 E 4 4 1 2 1 L 2 3 1 O 3 4 1 V 4 1 1 E Sample Output Case 1: Cute Sangsang, Binbin will come with a donkey after travelling 4 meters and finding 1 LOVE strings at last. Case 2: Binbin you disappoint Sangsang again, damn it! Author FZU Source 2012 Multi-University Training Contest 7 SPFA LOVE trick

?Download sourceCode.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
 
using namespace std;
 
#define MAXN 9400
#define MAXM 90000
#define INF 1LL<<63-1
 
struct Edge{
    int v;
    int next;
    long long w;
    int id;
}edge[MAXM];
 
struct Point{
    int id;
    int u;
    Point(){}
    Point(int a, int b){
        u = a;
        id = b;
    }
};
 
int e, n, m, lastshow[MAXN];
 
void insert(int x, int y, long long w, char c){
    edge[e].v = y;
    edge[e].w = w;
    edge[e].next = lastshow[x];
    if(c == 'L')
        edge[e].id = 0;
    else if(c == 'O')
        edge[e].id = 1;
    else if(c == 'V')
        edge[e].id = 2;
    else if(c == 'E')
        edge[e].id = 3;
    lastshow[x] = e ++;
}
 
long long d[MAXN][4];
int vis[MAXN][4], num[MAXN][4];
queue<Point>q;
 
void init(){
    while(!q.empty()){
        q.pop();
    }
    e = 0;
    memset(lastshow, -1, sizeof(lastshow));
}
 
void spfa(int src){
    for(int i = 1; i <= n; i ++){
        for(int j = 0; j < 4; j ++){
            d[i][j] = INF;
            vis[i][j] = 0;
            num[i][j] = 0;//vis
        }
    }
    vis[src][3] = 1;
    d[src][3] = 0;
    Point tmp = Point(src, 3);//idid
    q.push(tmp);
    while(!q.empty()){
        tmp = q.front();
        q.pop();
        int u = tmp.u;
        int id = tmp.id;
        vis[u][id] = 0;
        for(int i = lastshow[u]; i != -1; i = edge[i].next){//
            int v = edge[i].v;
            int x = edge[i].id;
            long long w = edge[i].w;
            if((d[u][id] + w <= d[v][x] || d[v][x] == 0) && (id + 1) % 4 == x){//
                if(num[v][x] > num[u][id] && d[u][id] + w == d[v][x])           //||d==0
                    continue;//num
                d[v][x] = d[u][id] + w;
                num[v][x] = num[u][id];
                if(x == 3)
                    num[v][x] ++;//LOVEnum
                if(!vis[v][x]){
                    q.push(Point(v, x));
                    vis[v][x] = 1;
                }
            }
        }
    }
}
 
char s[10];
 
int main(){
    int t, cas =0;
    scanf("%d", &t);
    while(t --){
        init();
        scanf("%d %d", &n, &m);
        int u, v, w;
        while(m --){
            scanf("%d %d %d %s", &u, &v, &w, s);
            insert(u, v, w, s[0]);
            insert(v, u, w, s[0]);
        }
        spfa(1);
        if(num[n][3] == 0 || d[n][3] == INF)
            printf("Case %d: Binbin you disappoint Sangsang again, damn it!\n", ++cas);
        else
            printf("Case %d: Cute Sangsang, Binbin will come with a donkey after travelling %I64d meters and finding %d LOVE strings at last.\n", ++cas, d[n][3], num[n][3]);
    }
    return 0;
}