2015
05-23

# As long as Binbin loves Sangsang

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 complete”LOVE” string.
Binbin is at node 1 and Sangsang is at node N.

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 1…N and M roads).
Then following M lines, each line has four variables“U V L letter”, means that there is a road between city U,V(1<=U,V<=N) with length L and the letter marked is‘L’,’O’,’V’ or ‘E’

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 1…N and M roads).
Then following M lines, each line has four variables“U V L letter”, means that there is a road between city U,V(1<=U,V<=N) with length L and the letter marked is‘L’,’O’,’V’ or ‘E’

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

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!

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
using namespace std;
#define NMAX 1317
#define MMAX 13525
#define oo 1000000000000000LL
struct node
{
int to,next,w;
} e[MMAX<<1];
int n,m;
bool vis[NMAX<<2];
long long dis[NMAX<<2];
int ds[NMAX<<2];
queue<int>q;
int L[4];
void init()
{
edge=0;
}
inline int f(char a)
{
if(a=='L') return 0;
if(a=='O') return 1;
if(a=='V') return 2;
return 3;
}
{
}
bool spfa()
{
int v,i;
while(!q.empty()) q.pop();
for(i=0; i<4*n; i++)
{
dis[i]=(i==0?0:oo);
ds[i]=(i==0?0:MMAX);
}
memset(vis,0,sizeof(vis));
vis[0]=1;
q.push(0);
while(!q.empty())
{
int tmp=q.front();
q.pop();
{
if(dis[tmp]+e[i].w<=dis[v=e[i].to])
{
if(dis[tmp]+e[i].w<dis[v])
{
dis[v]=dis[tmp]+e[i].w;
ds[v]=ds[tmp]+1;
}
else
ds[v]=max(ds[tmp]+1,ds[v]);
if(!vis[v])
{
vis[v]=true;
q.push(v);
}
}
}
vis[tmp]=false;
}
return true;
}
int main()
{
int t,u,v,l;
char ch[5];
scanf("%d",&t);
for(int ca=1; ca<=t; ca++)
{
init();
scanf("%d%d",&n,&m);
for(int i=0;i<4;i++) L[i]=100000000;
for(int i=0; i<m; i++)
{
scanf("%d%d%d%s",&u,&v,&l,ch);
int t1=f(ch[0]);
int t2=t1+1>3?0:t1+1;
L[t1]=min(L[t1],l);
}
spfa();
printf("Case %d: ",ca);
if(n>1)
{
if(dis[4*(n-1)]<oo)
printf("Cute Sangsang, Binbin will come with a donkey after travelling %I64d meters and finding %d LOVE strings at last.\n",dis[4*(n-1)],ds[4*(n-1)]/4);
else puts("Binbin you disappoint Sangsang again, damn it!");
}
else {
int ans=0;
for(int i=0;i<4;i++)
ans+=L[i];
if(ans>100000000) puts("Binbin you disappoint Sangsang again, damn it!");
else printf("Cute Sangsang, Binbin will come with a donkey after travelling %d meters and finding 1 LOVE strings at last.\n",ans);
}
}
return 0;
}

1. 区别是大学生一年就那么多，蓝领哪一行竞争都比读书激烈，绝大多数又可替代性强，自然待遇下降，等人力***严重匮乏，蓝领行业附加值高的时候又不一样了，但国内怕是等不到这一天

2. 区别是大学生一年就那么多，蓝领哪一行竞争都比读书激烈，绝大多数又可替代性强，自然待遇下降，等人力***严重匮乏，蓝领行业附加值高的时候又不一样了，但国内怕是等不到这一天

3. 区别是大学生一年就那么多，蓝领哪一行竞争都比读书激烈，绝大多数又可替代性强，自然待遇下降，等人力***严重匮乏，蓝领行业附加值高的时候又不一样了，但国内怕是等不到这一天

4. 区别是大学生一年就那么多，蓝领哪一行竞争都比读书激烈，绝大多数又可替代性强，自然待遇下降，等人力***严重匮乏，蓝领行业附加值高的时候又不一样了，但国内怕是等不到这一天

5. 区别是大学生一年就那么多，蓝领哪一行竞争都比读书激烈，绝大多数又可替代性强，自然待遇下降，等人力***严重匮乏，蓝领行业附加值高的时候又不一样了，但国内怕是等不到这一天

6. 区别是大学生一年就那么多，蓝领哪一行竞争都比读书激烈，绝大多数又可替代性强，自然待遇下降，等人力***严重匮乏，蓝领行业附加值高的时候又不一样了，但国内怕是等不到这一天

7. 区别是大学生一年就那么多，蓝领哪一行竞争都比读书激烈，绝大多数又可替代性强，自然待遇下降，等人力***严重匮乏，蓝领行业附加值高的时候又不一样了，但国内怕是等不到这一天

8. 区别是大学生一年就那么多，蓝领哪一行竞争都比读书激烈，绝大多数又可替代性强，自然待遇下降，等人力***严重匮乏，蓝领行业附加值高的时候又不一样了，但国内怕是等不到这一天