10537 - The Toll! Revisited

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Sep 02, 2003 8:52 am

Thanks Per! That was right in my blind spot! Got AC now.
Shahriar: It was unlikely, but miras 'sounded' very convincing...
miras: did you realy get AC with that?

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Mon Sep 15, 2003 3:27 pm

eloo



is cyfa right??
i dont know i tried to submit my code once again byt it gives Compile Error ?
Hm what is going on
BTW miras =man :D
___________
made the force be with you

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Mon Sep 15, 2003 3:27 pm

eloo



is cyfa right??
i dont know i tried to submit my code once again byt it gives Compile Error ?
Hm what is going on
BTW miras =man :D
___________
made the force be with you

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Mon Sep 15, 2003 3:44 pm

oh can i send tasks which schould be compile in Free Pascal? :evil:

oxoxoxox
New poster
Posts: 2
Joined: Wed Dec 31, 2003 11:56 pm

10537 - Toll! Revisited [WA]

Post by oxoxoxox » Thu Jan 01, 2004 4:02 am

i got WA....help~~

[java]
import java.util.*;
import java.io.*;

class Main {


public void Begin() {
String tmpstr;
StringTokenizer st;

int casenum = 1;
while((tmpstr = Main.ReadLn(255)) != null) {
st = new StringTokenizer(tmpstr);
if(st.nextToken().equals("-1"))
break;

int roadnum = Integer.parseInt(
(new StringTokenizer(tmpstr)).nextToken());

int start,
end;
graph = new boolean[52][52];
//read two endpoints of a road
for(int i = 0 ;i < roadnum; i++) {
st = new StringTokenizer(ReadLn(255));
start = countVertexNum(st.nextToken().charAt(0));
end = countVertexNum(st.nextToken().charAt(0));
graph[start][end] = true;
graph[end][start] = true;
}
st = new StringTokenizer(ReadLn(255));
long spoons = Long.parseLong(st.nextToken());
start = countVertexNum(st.nextToken().charAt(0));
end = countVertexNum(st.nextToken().charAt(0));

Dijkstra(end,spoons);


//output data
int[] path = new int[52];
int pathnum = 0,
backtrackp = start;
while(backtrackp != end) {
path[pathnum++] = backtrackp;
backtrackp = parentVertex[backtrackp];
}
path[pathnum++] = backtrackp;

System.out.println("Case " +casenum+":");
System.out.println(""+VertexNowCost[start]);
String result = "" + countVertexLetter(path[0]);
for(int i = 1; i < pathnum ; i++)
result += "-" + countVertexLetter(path);
System.out.println(result);
casenum++;
}

}

boolean[][] graph;
boolean[] passed;
long[] VertexNowCost;
int parentVertex[];
public void Dijkstra(int start,long spoons) {

passed = new boolean[graph.length];
parentVertex = new int[graph.length];
VertexNowCost = new long[graph.length];
for(int i = 0; i < VertexNowCost.length; i++)
VertexNowCost = Long.MAX_VALUE;
queue = new Vector(0);

VertexNowCost[start] = spoons;
QueueAdd(start,spoons);
while(!QueueIsempty()) {
int nowVertex = QueueGet();
passed[nowVertex] = true;

long addcost;
long nowcost = VertexNowCost[nowVertex];
if(nowVertex<=25){//town
nowcost = nowcost*20/19;
if(VertexNowCost[nowVertex]%19 != 0)
nowcost++;
addcost = nowcost - VertexNowCost[nowVertex];
nowcost = VertexNowCost[nowVertex];
}
else //valliage
addcost = 1;

if(nowcost == 0)
addcost = 1;
for(int i = 0; i < graph.length; i++) {
if( !passed && graph[nowVertex]){
if(nowcost + addcost < VertexNowCost){
parentVertex = nowVertex;
VertexNowCost = nowcost + addcost;
QueueAdd(i,VertexNowCost);
}
else if(nowcost + addcost == VertexNowCost){
if(nowVertex < parentVertex)
parentVertex[i] = nowVertex;
}
}
}
}
}
int countVertexNum(char letter) {
int ascii = (int)letter;

if(ascii >= 65 && ascii <= 90)
ascii -= 90;
else if(ascii >= 97 && ascii <=122)
ascii -= 148; //122+26

return -ascii;
}
char countVertexLetter(int num) {
if(num >= 26) {
num -= 51;
num *= -1;
num += 97;
return (char)num;
}
else {
num -= 25;
num *= -1;
num += 65;
return (char)num;
}
}

/*Queue*/
Vector queue = new Vector(0);
public void QueueAdd(int vertex,long cost) {
int i = 0;
QueueElement qe;
for(; i < queue.size(); i++) {
qe = (QueueElement)queue.elementAt(i);
if(qe.priority >= cost)
break;
}
queue.insertElementAt(new QueueElement(vertex,cost),i);
}
public int QueueGet() {
QueueElement qe;

if(queue.size() == 0)
return -1;

qe = (QueueElement)queue.elementAt(0);
queue.removeElementAt(0);
return qe.data;
}

public boolean QueueIsempty() {
return queue.size() == 0;
}

static String ReadLn (int maxLg){
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try {
while (lg < maxLg){
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (Exception e){
return (null);
}

if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}

public static void main (String args[]) {
Main myWork= new Main();
myWork.Begin();
}
}


class QueueElement{
int data;
long priority;
public QueueElement(int d, long p) {
data = d;
priority = p;
}
}
[/java]

oxoxoxox
New poster
Posts: 2
Joined: Wed Dec 31, 2003 11:56 pm

testcase and my answer

Post by oxoxoxox » Thu Jan 01, 2004 4:14 am

i have completed the fellowing cases

Code: Select all

0 
2 A A
25  
A B
B C
C D
D E
E F
F G
G H
H I
I J
J K
K L
L M
M N 
N O
O P
P Q
Q R
R S
S T
T U
U V
V W
W X
X Y
Y Z
999999999 A Z
4 
A b 
A B 
b c 
B c 
18 A c
4
A b 
A B 
b c 
B c 
19 A c
5
A D
D X
A b
b c
c X
39 A X
-1

Code: Select all

Case 1:
2
A
Case 2:
3605038190
A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z
Case 3:
20
A-B-c
Case 4:
21
A-b-c
Case 5:
44
A-b-c-X

virtuala
New poster
Posts: 1
Joined: Sun Mar 14, 2004 5:51 pm

10537 Toll Revisited

Post by virtuala » Fri Mar 19, 2004 8:37 pm

Hi,
I got Wrong Ans but i alredy checked various test cases and got correct answers. but judge says wrong answer .

can any body help me please?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Sun Mar 21, 2004 10:51 am

did you consider if source = destination?+

-titid besar-
Kalo mau kaya, buat apa sekolah?

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Tue Aug 15, 2006 5:23 am

http://acm.uva.es/p/v105/10537.html

Hello..~
I got "Output Limit Exceeded" don't know why..
It's ok for sample input.. any idea..?

Code: Select all

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cctype>
#define INF 9999999999999999LL
using namespace std;
int comp(char a, char b)
{
        char x, y;
        x = tolower(a);
        y = tolower(b);
        if (x != y) {
                if (x > y)
                        return 1;
                return 0;
        }
        if (a > b)
                return 1;
        return 0;
}
int main()
{
        int map[128][128];
        int i, j, k, n;
        char ch1[4], ch2[4], src, dest;
        long long check[128], p;
        char path[128];
        int cn = 1;
        while (scanf("%d", &n) && n != -1) {
                memset(map, 0, sizeof(map));
                for (i = 0; i < n; i++) {
                        scanf("%s%s", ch1, ch2);
                        map[*ch1][*ch2] = map[*ch2][*ch1] = 1;
                }
                scanf("%lld%s%s", &p, ch1, ch2);
                src = *ch1;
                dest = *ch2;

                for (i = 'A'; i <= 'z'; i++)
                        check[i] = INF;
                memset(path, 0, sizeof(path));

                queue<int> q;
                q.push(dest);
                check[dest] = p;
                while (!q.empty()) {
                        k = q.front();
                        q.pop();
                        if (k >= 'a') {
                                for (i = 'A'; i <= 'z'; i++) {
                                        if (map[i][k] && check[i] == check[k] + 1) {
                                                if (comp(path[i], k))
                                                        path[i] = k;
                                        }
                                        if (map[i][k] && check[i] > check[k]+1) {
                                                check[i] = check[k]+1;
                                                path[i] = k;
                                                q.push(i);
                                        }
                                }
                        }
                        else {
                                for (i = 'A'; i <= 'z'; i++) {
                                        j = (int)ceil((double)(check[k]*20)/(double)19);
                                        if (map[i][k] && check[i] == j) {
                                                if (comp(path[i], k))
                                                        path[i] = k;
                                        }
                                        if (map[i][k] && check[i] > j) {
                                                check[i] = j;
                                                path[i] = k;
                                                q.push(i);
                                        }
                                }
                        }
                }
                printf("Case %d:\n", cn++);
                printf("%lld\n", check[src]);

                i = src;
                printf("%c", src);
                while (i != dest) {
                        printf("-%c", path[i]);
                        i = path[i];
                }
                printf("\n");
        }
        return 0;
}

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 10537 - The Toll! Revisited

Post by red_apricot » Wed May 13, 2015 5:04 pm

I'm pretty sure my code is fine, but it gets WA. I've solved the "original" live-archive counterpart, but this one...

Code: Select all

/*
 * 10537. The Toll! Revisited
 */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define N 0x80
#define Q (2*N)
#define xchg(x,y) (((x)==(y))||((x)^=(y),(y)^=(x),(x)^=(y)))
#define bubble (xchg(pos[heap[i]],pos[heap[j]]),xchg(heap[i],heap[j]))
#define oo (1LL<<43)
typedef long long i64;

int cs,n,is[256],yes,g[256][256],m,id[256],a[N][N],src,dst,heap[Q],pos[N],cnt,p[N],pr;
i64 d[N],de;
char v[256],prev;

void push( int x ) {
	int i,j;
	if ( pos[x] < 0 ) pos[heap[cnt]=x]=cnt,++cnt;
	for ( j = pos[x]; j && d[heap[i=(j-1)>>1]] < d[heap[j]]; bubble, j = i );
}

int pop() {
	int i,j,x = *heap;
	if ( (pos[x]=-1),--cnt )
		pos[*heap = heap[cnt]] = 0;
	for ( j = 0; (i=j,j<<=1,++j) < cnt; bubble ) {
		if ( j < cnt-1 && d[heap[j]] < d[heap[j+1]] ) ++j;
		if ( d[heap[i]] >= d[heap[j]] ) break ;
	}
	return x;
}

int is_city( int x ) { 
	assert( isalpha(v[x>>1]) );
	return 'A' <= v[x>>1] && v[x>>1] <= 'Z';
}

i64 toll( i64 T, int x ) {
	if ( (x&1) ) return 0;
	if ( is_city(x) ) {
		if ( T%20 ) T /= 20, ++T;
		else T /= 20;
		return T;
	}
	return 1;
}

i64 dijk( int src, int dst, i64 D ) {
	int x,y,i,j,k,t;
	i64 dw;
	for ( x = 0; x < n; ++x ) d[x] = -oo;
	for ( cnt = 0, memset(pos,-1,sizeof pos), p[src] = -1, d[src] = D, push(src); cnt && d[dst] == -oo; )
		for ( x = pop(), y = 0; x != dst && y < (n>>1); ++y )
			for ( t = 0; t <= 1; ++t )
			if ( a[x][t|(y<<1)] ) {
				dw = toll(d[x],t|(y<<1));
				if ( d[x]-dw >= 0 && d[t|(y<<1)] < d[x]-dw )
					d[t|(y<<1)] = d[x]-dw, p[t|(y<<1)] = x, push(t|(y<<1));
			}
	return d[dst];
}

void dump( int src, int x ) {
	if ( p[x] != -1 ) dump(src,p[x]);
	if ( prev == v[x>>1] ) return ;
	if ( ++pr > 1 ) putchar('-');
	printf("%c",prev = v[x>>1]);
}

int main() {
	int i,j,k,src,dst;
	char tmp0[0x20],tmp1[0x20];
	i64 low,high,mid,ans;
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
#endif
	for ( ;1 == scanf("%d",&n) && n != -1 && ++yes; ) {
		printf("Case %d:\n",++cs);
		for ( k = 0; k < n; ++k ) {
			scanf("%s %s",tmp0,tmp1);
			is[*tmp0] = is[*tmp1] = yes;
			g[*tmp0][*tmp1] = g[*tmp1][*tmp0] = yes;
		}
		for ( n = 0, i = 'A'; i <= 'Z'; ++i )
			if ( is[i] == yes ) v[id[i] = n++] = i;
		for ( i = 'a'; i <= 'z'; ++i )
			if ( is[i] == yes ) v[id[i] = n++] = i;
		memset(a,0,sizeof a);
		for ( i = 0; i < n; ++i )
			for ( j = 0; j < n; ++j )
				if ( g[v[i]][v[j]] == yes )
					a[1|(i<<1)][0|(j<<1)]=1;
		for ( i = 0; i < n; ++i )
			a[0|(i<<1)][1|(i<<1)] = 1;
		scanf("%lld %s %s",&de,tmp0,tmp1), n<<=1;
		src = (1|(id[*tmp0]<<1)), dst = (1|(id[*tmp1]<<1));
		if ( src == dst ) {
			printf("%lld\n%c\n",de,*tmp0);
			continue ;
		}
		if ( dijk(src,dst,low=0) >= de ) 
			ans = low;
		else {
			for ( low = 0, high = +oo; low+1 != high; )
				if ( dijk(src,dst,mid=(low+high)>>1)<de )
					low = mid;
				else high = mid;
			ans = high;
		}
		dijk(src,dst,ans);
		printf("%lld\n",ans);
		/*assert( dijk(src,dst,low)   < de );
		assert( dijk(src,dst,high) >= de );*/
		dijk(src,dst,ans);
		prev = -1, pr = 0, dump(src,dst);
		putchar('\n');
	}
    return 0;
}


red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 10537 - The Toll! Revisited

Post by red_apricot » Thu May 14, 2015 8:13 pm

This is my updated code. Now I compare two paths explicitly. On random tests the output is identical to that of udebug.com. Still WA.
BTW we no longer can edit/delete out posts?

Code: Select all

/*
 * 10537. The Toll! Revisited
 * TOPIC: dijkstra, binary search, comparison function, binary heap with update, printing the path, lex order
 */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define N 0x100
#define Q (2*N)
#define xchg(x,y) (((x)==(y))||((x)^=(y),(y)^=(x),(x)^=(y)))
#define bubble (xchg(pos[heap[i]],pos[heap[j]]),xchg(heap[i],heap[j]))
#define oo (1LL<<61)
typedef long long i64;
#define in(x)  (0|((x)<<1))
#define out(x) (1|((x)<<1))

int cs,n,is[256],yes,g[256][256],m,id[256],a[N][N],src,dst,heap[Q],pos[N],cnt,p[N],pr,
	deg[N],adj[N][N],seen[N];
i64 d[N],de;
char v[256],prev;

int cmp( int x, int y ) {
	/*
	if ( v[x>>1] == v[y>>1] ) {
		if ( d[x] == d[y] )
			return 0;
		if ( d[x] > d[y] )
			return -1;
		return 1;
	}
	if ( v[x>>1] < v[y>>1] )
		return -1;
	return 1;
	*/
	if ( d[x] == d[y] ) {
		if ( v[x>>1] == v[y>>1] )
			return 0;
		if ( v[x>>1] < v[y>>1] )
			return -1;
		return 1;
	}
	if ( d[x] > d[y] )
		return -1;
	return 1;
}

void push( int x ) {
	int i,j;
	if ( pos[x] < 0 ) pos[heap[cnt]=x]=cnt,++cnt;
	for ( j = pos[x]; j && cmp(heap[i=(j-1)>>1],heap[j]) > 0; bubble, j = i );
}

int pop() {
	int i,j,x = *heap;
	if ( (pos[x]=-1),--cnt )
		pos[*heap = heap[cnt]] = 0;
	for ( j = 0; (i=j,j<<=1,++j) < cnt; bubble ) {
		if ( j < cnt-1 && cmp(heap[j],heap[j+1]) > 0 ) ++j;
		if ( cmp(heap[i],heap[j]) <= 0 ) break ;
	}
	return x;
}

int is_city( int x ) { 
	assert( isalpha(v[x>>1]) );
	return 'A'<=v[x>>1]&&v[x>>1]<='Z';
}

i64 toll( i64 T, int x ) {
	if ( x&1 ) return 0;
	if ( is_city(x) ) {
		if ( T%20 ) T /= 20, ++T;
		else T /= 20;
		return T;
	}
	return 1;
}

i64 dijk( int src, int dst, i64 D ) {
	int x,y,z,i,j,k,t;
	i64 dw;
	for ( x = 0; x < n; d[x++] = -oo );
	for ( cnt = 0, memset(pos,-1,sizeof pos), p[src] = -1, d[src] = D, push(src); cnt; )
		for ( x = pop(), i = 0; i < deg[x] && (z = adj[x][i]) >= 0; ++i )
			if ( d[z] < d[x]-(dw = toll(d[x],z)) )
				d[z] = d[p[z]=x]-dw, push(z);
	return d[dst];
}

void dump( int src, int x ) {
	if ( p[x] != -1 ) dump(src,p[x]);
	if ( prev == v[x>>1] ) return ;
	if ( ++pr > 1 ) putchar('-');
	printf("%c",prev = v[x>>1]);
}

int q[1 << 20],*head,*tail;

int lex_smaller( int x, int y ) {
	int path[2][N],*ptr[2],z,i,j,k,t;
	ptr[0] = path[0], ptr[1] = path[1];
	for ( z = x; z != -1; *ptr[0]++ = z, z = p[z] );
	for ( z = y; z != -1; *ptr[1]++ = z, z = p[z] );
	for ( k = 0; k < 2; ++k )
		for ( i = 0, j = ptr[k]-path[k]-1; i < j; ++i, --j )
			t = path[k][i], path[k][i] = path[k][j], path[k][j] = t;
	for ( i = 0; i < ptr[0]-path[0] && i < ptr[1]-path[1]; ++i )
		if ( path[0][i] != path[1][i] )
			return path[0][i] < path[1][i];
	return ptr[0]-path[0] < ptr[1]-path[1];
}

void bfs( int src, int dst, i64 D ) {
	int x,y,i;
	i64 dw;
	for ( x = 0; x < n; d[x++] = -oo );
	for ( head = tail = q, d[*tail++ = src] = D; head < tail; )
		for ( x = *head++, i = 0; i < deg[x] && d[x] >= de; ++i )
			if ( d[y = adj[x][i]] < d[x]-(dw = toll(d[x],y)) || (d[y] == d[x]-dw && lex_smaller(x,p[y])) )
				d[*tail++ = y] = d[p[y] = x]-dw;
}

int dfs( int dst, int x, i64 D ) {
	int y,i;
	if ( x == dst && D == de )
		return 1;
	if ( x == dst ||  D < de ) 
		return 0;
	for ( i = 0; i < deg[x] && (y=adj[x][i]) >= 0; ++i )
		if ( seen[y] != yes ) {
			p[y] = x, seen[y] = yes;
			if ( dfs(dst,y,D-toll(D,y)) )
				return 1;
			seen[y] = 0;
		}
	return 0;
}

int main() {
	int i,j,k,src,dst;
	char tmp0[0x20],tmp1[0x20];
	i64 low,high,mid,ans;
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
#endif
	for ( ;1 == scanf("%d",&n) && n != -1 && ++yes; ) {
		printf("Case %d:\n",++cs);
		for ( k = 0; k < n; ++k ) {
			scanf("%s %s",tmp0,tmp1);
			/*if ( *tmp0 == *tmp1 ) continue ;*/
			is[*tmp0] = is[*tmp1] = yes;
			g[*tmp0][*tmp1] = g[*tmp1][*tmp0] = yes;
		}
		for ( n = 0, i = 'A'; i <= 'Z'; ++i )
			if ( is[i] == yes ) v[id[i] = n++] = i;
		for ( i = 'a'; i <= 'z'; ++i )
			if ( is[i] == yes ) v[id[i] = n++] = i;
		memset(a,0,sizeof a);
		for ( i = 0; i < n; ++i )
			for ( j = 0; j < n; ++j )
				if ( g[v[i]][v[j]]==yes )
					a[out(i)][in(j)]=1;
		for ( i = 0; i < n; ++i ) a[in(i)][out(i)]=1;
		for ( n <<= 1, i = 0; i < n; ++i )
			for ( deg[i] = 0, j = 0; j < n; ++j )
				if ( a[i][j] )
					adj[i][deg[i]++] = j;
		scanf("%lld %s %s",&de,tmp0,tmp1);
		src = out(id[*tmp0]), dst = out(id[*tmp1]);
		if ( dijk(src,dst,low=0) >= de ) 
			ans = low;
		else {
			for ( low = 0, high = +oo; low+1 != high; )
				if ( dijk(src,dst,mid=(low>>1)+(high>>1))<de )
					low = mid;
				else high = mid;
			ans = high;
		}
		bfs(src,dst,ans);
		printf("%lld\n",ans);
		prev = -1, pr = 0, dump(src,dst);
		putchar('\n');
	}
    return 0;
}

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 10537 - The Toll! Revisited

Post by red_apricot » Fri May 15, 2015 11:03 am

OK, got AC, never mind my previous posts.

Tanmoy1228
New poster
Posts: 10
Joined: Sat Jul 19, 2014 2:55 am

Re: 10537 - The Toll! Revisited

Post by Tanmoy1228 » Tue Sep 22, 2015 9:43 pm

Verdict: WA
can not get the problem..
please help......

Code: Select all

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define sc(a) scanf("%lld",&a)
bool visit[100000];
vector<ll>graph[10000];
ll des,deliver,strt,m,ok;
vector<ll>par,par1;
bool bfs(ll sum)
{
    ll u,v,i,l,dis[1000];
    queue<ll>Q;
    Q.push(strt);
    memset(dis,0,sizeof dis);
    dis[strt]=sum;
    while(!Q.empty())
    {
        u=Q.front();
        Q.pop();
        for(i=0; i<graph[u].size(); i++)
        {
            v=graph[u][i];
            if(v>96)
            {
                if((dis[v]<dis[u]-1) || ((dis[v]==dis[u]-1) && u<par[v]))
                {
                    dis[v]=dis[u]-1;
                    Q.push(v);
                    par[v]=u;
                    //cout<<char(u)<<" "<<char(v)<<endl;
                }
            }
            else
            {
                if(dis[v]<(dis[u]-ceil(dis[u]*0.05)) || (dis[v]==(dis[u]-ceil(dis[u]*0.05)) && u<par[v]))
                if(dis[v]<(dis[u]-ceil(dis[u]*0.05)))
                {
                    dis[v]=dis[u]-ceil(dis[u]*0.05);
                    Q.push(v);
                    par[v]=u;
                    //cout<<char(u)<<" "<<char(v)<<endl;
                }
            }
        }
    }
    if(dis[des]>=deliver)
        return true;
    else
        return false;
}

ll Binary_Search()
{
    ll low,high,mid,ans;
    low=0;
    high=pow(10,10);

    while(low<=high)
    {
        mid=(low+high)/2;
        memset(visit,false,sizeof visit);
        ok=-1;
        if(bfs(mid))
        {
            ans=mid;
            par1=par;
            par.assign(1000,-1);
            high=mid-1;
        }
        else
        {
            low=mid+1;
        }
    }
    return ans;
}

int main()
{
    ll n,i,j,u,v,ans,t=0;
    char ch1,ch2;
    while(cin>>n)
    {
        if(n==-1)
            break;
        t++;
        par.assign(1000,-1);
        par1.assign(1000,-1);
        for(i=0; i<=200; i++)
            graph[i].clear();
        for(i=0; i<n; i++)
        {
            cin>>ch1>>ch2;
            u=ch1;
            v=ch2;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        cin>>m>>ch1>>ch2;
        strt=ch1;
        des=ch2;
        deliver=m;
        ans=Binary_Search();
        printf("Case %lld:\n%lld\n%c",t,ans,strt);
        par.clear();
        u=des;
        par.push_back(u);

        while(u!=strt)
        {
            u=par1[u];
            par.push_back(u);
        }
        reverse(par.begin(),par.end());

        for(i=1;i<par.size();i++)
            printf("-%c",par[i]);
        cout<<endl;
    }
    return 0;
}

Post Reply

Return to “Volume 105 (10500-10599)”