学步园

题目地址： http://acm.hdu.edu.cn/showproblem.php?pid=4360

2012 年多校 第7场， 1001 。

方法： 优先队列 + SPFA 

基础题。。。。   Trick 是，最终结果会爆int （有的数据需要重复兜圈）。。。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>

using namespace std;

const __int64 inf = (__int64)0x7ffffff * 0x7ffffff;

int pp[100];

struct Point{
	int x,p,num;
	__int64 cost;
	bool friend operator<(Point a,Point b){
		return a.cost!=b.cost?a.cost>b.cost:a.num<b.num;
	}
}res; 

priority_queue<Point>que;

struct Edge{
	int t,nxt,len,p;
}eg[30000];
int et[2000],tol;

void add_edge(int u,int v,int l,char p){
	eg[tol].t=v;
	eg[tol].nxt=et[u];
	eg[tol].len=l;
	eg[tol].p=pp[p];
	et[u]=tol++;
}

__int64 dis[2000][4];
int num[2000][4];

void init_(int n){
	for(int i=1;i<=n;i++){
		et[i]=-1;
		for(int j=0;j<4;j++)
			dis[i][j]=inf,num[i][j]=0;
	}
	tol=0;
	while(!que.empty()) que.pop();
}

int spfa(int x,int n){
	Point no,nx;
	int i;
	no.x=x,no.p=-1,no.num=0,no.cost=0;
	que.push(no);
	while(!que.empty()){
		no=que.top();
		que.pop();
		if(no.x==n && no.p==3){
			res=no;
			return 1;
		}
		for(i=et[no.x];i!=-1;i=eg[i].nxt){
			nx.p=no.p+1;	
			if(nx.p==4) nx.p=0;
			if(eg[i].p!=nx.p) continue;
			nx.x=eg[i].t;
			nx.cost=no.cost+eg[i].len;
			nx.num=no.num;
			if(nx.p==3) nx.num++; 
			if(dis[nx.x][nx.p]<nx.cost || dis[nx.x][nx.p]==nx.cost && num[nx.x][nx.p]>=nx.num) continue;
			dis[nx.x][nx.p]=nx.cost;
			num[nx.x][nx.p]=nx.num;
			que.push(nx);
		}
		
	}
	return 0;
}

int main(){
	int n,m,t,tt=1;
	int u,v,len;
	char op[2];
	pp['L']=0,pp['O']=1,pp['V']=2,pp['E']=3;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		init_(n);
		while(m--){
			scanf("%d%d%d%s",&u,&v,&len,op);
			add_edge(u,v,len,op[0]);
			if(u!=v) add_edge(v,u,len,op[0]);
		}
		printf("Case %d: ",tt++);
		if(spfa(1,n)) printf("Cute Sangsang, Binbin will come with a donkey after travelling %I64d meters and finding %d LOVE strings at last.",res.cost,res.num);
		else printf("Binbin you disappoint Sangsang again, damn it!");
		puts("");
	}
	return 0;
}
/*
2
9 12
1 3 2 L
3 5 2 O
5 7 2 V
7 9 2 E
1 2 1 L
2 3 1 O
3 4 1 V
4 5 1 E
5 6 1 L
6 7 1 O
7 8 1 V
8 9 1 E
1 4
1 1 1 L
1 1 1 O
1 1 1 V
1 1 1 E

*/