首页 > ACM题库 > HDU-杭电 > HDU 4360-As long as Binbin loves Sangsang[解题报告]HOJ
2015
05-23

HDU 4360-As long as Binbin loves Sangsang[解题报告]HOJ

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;
int head[NMAX<<2],edge;
bool vis[NMAX<<2];
long long dis[NMAX<<2];
int ds[NMAX<<2];
queue<int>q;
int L[4];
void init()
{
    memset(head,-1,sizeof(head));
    edge=0;
}
inline int f(char a)
{
    if(a=='L') return 0;
    if(a=='O') return 1;
    if(a=='V') return 2;
    return 3;
}
void add(int u,int v,int c)
{
    e[edge].to=v,e[edge].w=c,e[edge].next=head[u],head[u]=edge++;
}
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();
        for(i=head[tmp]; i!=-1; i=e[i].next)
        {
            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);
            add(4*(u-1)+t1,4*(v-1)+t2,l);
            add(4*(v-1)+t1,4*(u-1)+t2,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;
}