10537 - The Toll! Revisited
Moderator: Board moderators
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
10537 - Toll! Revisited [WA]
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]
[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]
testcase and my answer
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
10537 Toll Revisited
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?
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?
-
- Experienced poster
- Posts: 187
- Joined: Wed Dec 11, 2002 2:03 pm
- Location: Mount Papandayan, Garut
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..?
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;
}
-
- New poster
- Posts: 48
- Joined: Sun Jun 22, 2014 6:14 am
Re: 10537 - The Toll! Revisited
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;
}
-
- New poster
- Posts: 48
- Joined: Sun Jun 22, 2014 6:14 am
Re: 10537 - The Toll! Revisited
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?
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;
}
-
- New poster
- Posts: 48
- Joined: Sun Jun 22, 2014 6:14 am
Re: 10537 - The Toll! Revisited
OK, got AC, never mind my previous posts.
-
- New poster
- Posts: 10
- Joined: Sat Jul 19, 2014 2:55 am
Re: 10537 - The Toll! Revisited
Verdict: WA
can not get the problem..
please help......
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;
}