学步园

/*
分析：
    最短路小变异。
    好久没有敲最短路了，思维都死透了。。。
    对每个节点设立4个状态，分别表示“L”“LO”“LOV”“LOVE”，
代表前面的路径走过来带上这个点后、组成了什么，然后跑最
短路就行了，如果针对某个状态有多条dis相同的路径，那么
取LOVE最多的。
    另外，1可以往1走，俺系在系想不掉耶，还好从别的blog
挖掘出了点儿数据，囧~~~
    1
    1 4
    1 1 1 L
    1 1 1 O
    1 1 1 V
    1 1 1 E
    输出应该是4米、1个LOVE。。。

                                                     2013-04-10
*/

#include"iostream"
#include"cstdio"
#include"cstring"
#include"queue"
using namespace std;
const int N=1333;
const int M=13555;

int n,m;
int cnt[N][4];
__int64 dis[N][4];
struct Eage{
	int from,to,len,next,flag;
}eage[2*M];
int tot,head[N];
struct node{
	int a,b;
};

void add(int a,int b,int c,int d){
	eage[tot].from=a;eage[tot].to=b;eage[tot].len=c;eage[tot].flag=d;eage[tot].next=head[a];head[a]=tot++;
}
void get_map()
{
	int a,b,c,d;
	char str[11];
	tot=0;
	memset(head,-1,sizeof(head));
	while(m--)
	{
		scanf("%d%d%d%s",&a,&b,&c,str);
		if(str[0]=='L')		d=0;
		else if(str[0]=='O')d=1;
		else if(str[0]=='V')d=2;
		else				d=3;
		add(a,b,c,d);
		add(b,a,c,d);
	}
}
void SPFA()
{
	int i,l,j,t;
	int hash[N][4];
	__int64 temp=(__int64)1<<50;
	queue<node>q;
	node now,next;

	for(i=1;i<=n;i++)
	for(l=0;l<4;l++)
	{
		dis[i][l]=temp;
		cnt[i][l]=0;
		hash[i][l]=0;
	}

	now.a=1;now.b=0;
	q.push(now);
	hash[1][0]=1;

	while(!q.empty())
	{
		now=q.front();
		q.pop();
		for(j=head[now.a];j!=-1;j=eage[j].next)
		{
			if(eage[j].flag!=now.b)	continue;
			next.a=eage[j].to;
			next.b=now.b+1;
			if(next.b>3)	next.b=0;
			temp=dis[now.a][now.b]+eage[j].len;
			if(now.a==1 && now.b==0 && dis[1][0]==(__int64)1<<50)
				temp=eage[j].len;
			if(temp>dis[next.a][next.b])	continue;
			if(temp==dis[next.a][next.b])
			{
				t=cnt[now.a][now.b];
				if(!next.b)	t++;
				if(t>cnt[next.a][next.b])
				{
					cnt[next.a][next.b]=t;
					if(!hash[next.a][next.b])
					{
						q.push(next);
						hash[next.a][next.b]=1;
					}
				}
			}
			else
			{
				dis[next.a][next.b]=temp;
				cnt[next.a][next.b]=cnt[now.a][now.b];
				if(!next.b)	cnt[next.a][next.b]++;
				if(!hash[next.a][next.b])
				{
					q.push(next);
					hash[next.a][next.b]=1;
				}
			}
		}
		hash[now.a][now.b]=0;
	}
}
int main()
{
	int T,Case;
	cin>>T;
	for(Case=1;Case<=T;Case++)
	{
		scanf("%d%d",&n,&m);
		get_map();
		SPFA();
		if(!cnt[n][0])	printf("Case %d: Binbin you disappoint Sangsang again, damn it!\n",Case);
		else			printf("Case %d: Cute Sangsang, Binbin will come with a donkey after travelling %I64d meters and finding %d LOVE strings at last.\n",Case,dis[n][0],cnt[n][0]);
	}
	return 0;
}