UVA - 1027 Toll (UVALive - 2730, World Finals >> 2003 - Beverly Hills)

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int cost[55];
vector<int>adj[55];
int charToInt(char ch)
{
    if(ch>='A' && ch<='Z')  return ch-'A'+1;
    return ch - 'a' + 27;
}

int findCost(int w, int x)
{
    if(x>26) return 1;
//    if(w+w/20+1>w/20*20+20) return w/20+2;
//    return w/20+1;
    return (int) ceil(w*20.0/19)-w;
}

int bellman(int w, int st, int ed)
{

    for(int i=1; i<=52; i++)   cost[i]=1e9;
    cost[st]=w;

    for(int i=0; i<51; i++)
        for(int j=1; j<=52; j++)
            for(int k=0;k<adj[j].size();k++)
            {
                w = findCost(cost[j], j);
                cost[adj[j][k]] = min(cost[adj[j][k]], cost[j]+w);
            }
return cost[ed];
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1, n, u, v, st, ed, w;
    string s;
    char ch, ch2;
    while(cin>>n && n!=-1)
    {
        for(int i=0;i<n;i++)
        {
            cin>>ch>>ch2;
            u = charToInt(ch);
            v = charToInt(ch2);
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        cin>>w>>ch>>ch2;
        ed = charToInt(ch);
        st = charToInt(ch2);
        cout<< "Case "<<kk++<<": "<<bellman(w, st, ed) <<"\n";

        for(int i=1;i<=52;i++)  adj[i].clear();
    }
return 0;
}