gistfile1.txt

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>
#define MAX 1000000000000000LL
using namespace std;
int n, ct;
int main(){
    //freopen("in.c", "r", stdin);
    //freopen("out", "w", stdout);
    while(cin >> n, n >= 0){
        int adj[128][128] = {}, st, ed, in[128] = {}, path[128] = {};
        long long dis[128], item;
        char aa[10], bb[10];
        while(n--){
            cin >> aa >> bb;
            adj[aa[0]][bb[0]] = adj[bb[0]][aa[0]] = 1;
        }
        for(int i = 0; i < 128; i++)
            dis[i] = MAX;
        cin >> item >> aa >> bb;
        st = bb[0], ed = aa[0];
        dis[st] = item;
        queue<int>Q;
        Q.push(st);
        while(!Q.empty()){
            int x = Q.front(); Q.pop();
            in[x] = 0;
            for(int y = 0; y < 128; y++){
                if(adj[x][y]){
                    long long len = 0, temp = dis[x];
                    if(islower(x))
                        len = 1;
                    else{
                        len = MAX;
                         if(dis[x]%19==0)
                            len =  dis[x]*20/19 - dis[x];
                        else
                            len = (dis[x]*20/19 + 1) - dis[x];
                    }
                    //printf("(%c->%c)=%lld\n", x, y, dis[x] + len);

                    if(dis[x] + len < dis[y]){
                        dis[y] = dis[x] + len;
                        path[y] = x;
                        if(!in[y])
                            Q.push(y), in[y] = 1;
                        //printf("%c->%c\n", x, y);
                    }
                    else if(dis[x] + len == dis[y] && path[y] > x){
                        //printf("%c->%c\n", path[x], y);
                        path[y] = x;
                    }
                }
            }
        }
        printf("Case %d:\n", ++ct);
        printf("%lld\n", dis[ed]);
        vector<int>gg;
        //for(int i = 0; i < 128; i++)if(isalpha(i)&&path[i])
            //printf("(%c->%c) ", isalpha(i)?i:'0', path[i] ? path[i] : '0');puts("");
        //for(int x = st;x != ed; x=path[x])
            //gg.push_back(x);
        for(int i = ed; i !=st; i=path[i])
            printf("%c-", i);
        printf("%c", st);
        //for(int i = gg.size()-1; i >= 0; i--)
        	//printf("-%c", gg[i]);
		putchar(10);
    }
    return 0;
}

///http://online-judge.uva.es/board/viewtopic.php?f=25&t=3592&start=15