11280 - Flying to Fredericton

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

Moderator: Board moderators

m.shawkey
New poster
Posts: 9
Joined: Tue Jun 11, 2013 2:58 pm

Re: 11280 - Flying to Fredericton

Post by m.shawkey » Thu Aug 15, 2013 3:33 pm

I got two wrong answers because of this test case

input

Code: Select all

1 
2
Calgary
Fredericton
1
Calgary Fredericton 0
1 1


output

Code: Select all

Scenario #1
Total cost of flight(s) is $0
you do not need to sort the edges, instead do relaxation (Bellman Ford) as long as you can.

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Wrong Answer: 11280 - Flying to Fredericton

Post by raj » Tue Nov 19, 2013 12:31 am

Anyone please help me Why I am getting Wrong Answer :( :(

Code: Select all

import java.io.*;
import java.util.*;

class IntegerPair4 implements Comparable{
	int node;
	int weight;
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		IntegerPair4 other = (IntegerPair4) obj;
		if (node != other.node)
			return false;
		if (weight != other.weight)
			return false;
		return true;
	}
	public IntegerPair4(int n,int w){
		node = n;
		weight = w;
	}
	public int compareTo(Object o){
		return this.weight - ((IntegerPair4)o).weight;
	}
}

public class Main{
	public static HashMap<Integer,Integer> j;
	public static int INF = 10000000;
	public static PrintWriter z;
	public static void BellmenFord(ArrayList<ArrayList<IntegerPair4>> graph,ArrayList<IntegerPair4> quries){
		PriorityQueue<IntegerPair4> ans = new PriorityQueue<IntegerPair4>();
		int [] d = new int[graph.size()]; // source 0 to link 1  weight is d[1](which shortest weight from source)
		Arrays.fill(d,INF); // firstly source to all distance are infinity
		d[0] = 0;           // source to distance itselt 0
		for(int u = 0;u<graph.size();u++){
        	for(int b = 0;b<graph.get(u).size();b++){
        		int v = graph.get(u).get(b).node;
        		int weight = graph.get(u).get(b).weight;
        		if(d[v]>d[u]+weight){
        			d[v] = d[u] +weight;
        		}
            }
        	if(!quries.isEmpty()){
        		if(j.get(u)!=null){
        			if(quries.contains(((new IntegerPair4(u,j.get(u)))))){
        				ans.add(new IntegerPair4(d[d.length-1],j.get(u)));
        				quries.remove(new IntegerPair4(u,j.get(u)));
        			}
        		}
        	}
        	else break;
        }
        
        while(!ans.isEmpty()){
        	int v = ans.poll().node;
        	if(v!=INF){
        		z.println("Total cost of flight(s) is $"+v); 
        	}
        	else{
        		z.println("No satisfactory flights");
        	}
        }
        
        for(int c = 0;c<quries.size();c++){
        	if(d[d.length-1]!=INF){
        		z.println("Total cost of flight(s) is $"+d[d.length-1]);
        	}
        	else{
        		z.println("No satisfactory flights");
        	}
        }
        
	}
	public static void main(String[] args)throws IOException {
		BufferedReader k = new BufferedReader(new InputStreamReader(System.in));
		//BufferedReader k = new BufferedReader(new FileReader("D:/Uva-input.txt.txt"));
		z = new PrintWriter(System.out);
		int T = Integer.valueOf(k.readLine());
		int test = 1;
		while(T-->0){
			k.readLine();
			int n = Integer.valueOf(k.readLine());
			HashMap<String,Integer> map = new HashMap<String,Integer>();
			j = new HashMap<Integer,Integer>();
			for(int c = 0;c<n;c++){
				map.put(k.readLine(),c);
			}
			
			ArrayList<ArrayList<IntegerPair4>> graph = new ArrayList<ArrayList<IntegerPair4>>();
			for(int c = 0;c<n;c++){
				ArrayList<IntegerPair4> nei = new ArrayList<IntegerPair4>();
				graph.add(nei);
			}
			
			int m = Integer.valueOf(k.readLine());
			while(m-->0){
				StringTokenizer s = new StringTokenizer(k.readLine());
				int u = Integer.valueOf(map.get(s.nextToken()));
				int v = Integer.valueOf(map.get(s.nextToken()));
				int weight = Integer.valueOf(s.nextToken());
				graph.get(u).add(new IntegerPair4(v,weight));
				graph.get(v).add(new IntegerPair4(u,weight));
			}
			
			StringTokenizer s = new StringTokenizer(k.readLine());
			ArrayList<IntegerPair4> quries = new ArrayList<IntegerPair4>();
			//HashMap<Integer,Integer> quries = new HashMap<Integer,Integer>();
			int c = 0;
			s.nextToken();
			while(s.hasMoreTokens()){
				int r = Integer.valueOf(s.nextToken());
				quries.add(new IntegerPair4(r,c));
				j.put(r,c);
				c++;
			}
			
			/*System.out.println(j.get(2));
			System.out.println(j.get(1));
			System.out.println(j.get(0));
			System.out.println(j.get(10));*/
			
			z.println("Scenario #"+(test++));
			
			BellmenFord(graph,quries);
			z.println();
		}
		z.flush();
	}
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11280 - Flying to Fredericton

Post by brianfry713 » Wed Nov 20, 2013 1:45 am

Output a blank line between scenarios. Don't print an extra blank line at the end.
Check input and AC output for thousands of problems on uDebug!

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Wrong Answer: 11280 - Flying to Fredericton

Post by raj » Wed Nov 20, 2013 5:07 am

Still Wrong Answer... :( What to do ?? :( :(

Code: Select all

import java.io.*;
import java.util.*;

class IntegerPair4 implements Comparable{
   int node;
   int weight;
   @Override
   public boolean equals(Object obj) {
      if (this == obj)
         return true;
      if (obj == null)
         return false;
      if (getClass() != obj.getClass())
         return false;
      IntegerPair4 other = (IntegerPair4) obj;
      if (node != other.node)
         return false;
      if (weight != other.weight)
         return false;
      return true;
   }
   public IntegerPair4(int n,int w){
      node = n;
      weight = w;
   }
   public int compareTo(Object o){
      return this.weight - ((IntegerPair4)o).weight;
   }
}

public class Main{
   public static HashMap<Integer,Integer> j;
   public static int INF = 10000000;
   public static PrintWriter z;
   public static void BellmenFord(ArrayList<ArrayList<IntegerPair4>> graph,ArrayList<IntegerPair4> quries){
      PriorityQueue<IntegerPair4> ans = new PriorityQueue<IntegerPair4>();
      int [] d = new int[graph.size()]; // source 0 to link 1  weight is d[1](which shortest weight from source)
      Arrays.fill(d,INF); // firstly source to all distance are infinity
      d[0] = 0;           // source to distance itselt 0
      for(int u = 0;u<graph.size();u++){
           for(int b = 0;b<graph.get(u).size();b++){
              int v = graph.get(u).get(b).node;
              int weight = graph.get(u).get(b).weight;
              if(d[v]>d[u]+weight){
                 d[v] = d[u] +weight;
              }
            }
           if(!quries.isEmpty()){
              if(j.get(u)!=null){
                 if(quries.contains(((new IntegerPair4(u,j.get(u)))))){
                    ans.add(new IntegerPair4(d[d.length-1],j.get(u)));
                    quries.remove(new IntegerPair4(u,j.get(u)));
                 }
              }
           }
           else break;
        }
       
        while(!ans.isEmpty()){
           int v = ans.poll().node;
           if(v!=INF){
              z.println("Total cost of flight(s) is $"+v);
           }
           else{
              z.println("No satisfactory flights");
           }
        }
       
        for(int c = 0;c<quries.size();c++){
           if(d[d.length-1]!=INF){
              z.println("Total cost of flight(s) is $"+d[d.length-1]);
           }
           else{
              z.println("No satisfactory flights");
           }
        }
       
   }
   public static void main(String[] args)throws IOException {
      BufferedReader k = new BufferedReader(new InputStreamReader(System.in));
      //BufferedReader k = new BufferedReader(new FileReader("D:/Uva-input.txt.txt"));
      z = new PrintWriter(System.out);
      int T = Integer.valueOf(k.readLine());
      int test = 1;
      while(T-->0){
         k.readLine();
         int n = Integer.valueOf(k.readLine());
         HashMap<String,Integer> map = new HashMap<String,Integer>();
         j = new HashMap<Integer,Integer>();
         for(int c = 0;c<n;c++){
            map.put(k.readLine(),c);
         }
         
         ArrayList<ArrayList<IntegerPair4>> graph = new ArrayList<ArrayList<IntegerPair4>>();
         for(int c = 0;c<n;c++){
            ArrayList<IntegerPair4> nei = new ArrayList<IntegerPair4>();
            graph.add(nei);
         }
         
         int m = Integer.valueOf(k.readLine());
         while(m-->0){
            StringTokenizer s = new StringTokenizer(k.readLine());
            int u = Integer.valueOf(map.get(s.nextToken()));
            int v = Integer.valueOf(map.get(s.nextToken()));
            int weight = Integer.valueOf(s.nextToken());
            graph.get(u).add(new IntegerPair4(v,weight));
            graph.get(v).add(new IntegerPair4(u,weight));
         }
         
         StringTokenizer s = new StringTokenizer(k.readLine());
         ArrayList<IntegerPair4> quries = new ArrayList<IntegerPair4>();
         //HashMap<Integer,Integer> quries = new HashMap<Integer,Integer>();
         int c = 0;
         s.nextToken();
         while(s.hasMoreTokens()){
            int r = Integer.valueOf(s.nextToken());
            quries.add(new IntegerPair4(r,c));
            j.put(r,c);
            c++;
         }
         
         /*System.out.println(j.get(2));
         System.out.println(j.get(1));
         System.out.println(j.get(0));
         System.out.println(j.get(10));*/
         
         z.println("Scenario #"+(test++));
         
         BellmenFord(graph,quries);
         if(T!=0) z.println();
      }
      z.flush();
   }
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11280 - Flying to Fredericton

Post by brianfry713 » Wed Nov 20, 2013 10:45 pm

Input:

Code: Select all

10

13
Calgary
fzCZuP
qPTOsTpAUciGo
Kszhnofktm
tKJAJlLtKVhea
Mc
yAtgWWWRKgdGC
FjQEfIEiYHknDkDZtNWI
sg
wWzeMpuXdgdjFGrQsUu
iyEFwFBYOwcA
mkmquCdMJFzJSNTI
Fredericton
33
Calgary fzCZuP 32
Calgary Kszhnofktm 198
Calgary tKJAJlLtKVhea 333
Calgary yAtgWWWRKgdGC 485
Calgary sg 520
Calgary wWzeMpuXdgdjFGrQsUu 644
Calgary Fredericton 484
fzCZuP yAtgWWWRKgdGC 409
fzCZuP FjQEfIEiYHknDkDZtNWI 424
fzCZuP sg 333
fzCZuP wWzeMpuXdgdjFGrQsUu 120
qPTOsTpAUciGo Mc 165
qPTOsTpAUciGo yAtgWWWRKgdGC 994
qPTOsTpAUciGo FjQEfIEiYHknDkDZtNWI 862
qPTOsTpAUciGo wWzeMpuXdgdjFGrQsUu 541
qPTOsTpAUciGo iyEFwFBYOwcA 294
qPTOsTpAUciGo mkmquCdMJFzJSNTI 960
Kszhnofktm Mc 275
Kszhnofktm sg 872
Kszhnofktm wWzeMpuXdgdjFGrQsUu 168
Kszhnofktm iyEFwFBYOwcA 660
Kszhnofktm mkmquCdMJFzJSNTI 266
tKJAJlLtKVhea sg 694
tKJAJlLtKVhea Fredericton 714
Mc yAtgWWWRKgdGC 264
Mc sg 262
Mc wWzeMpuXdgdjFGrQsUu 994
Mc iyEFwFBYOwcA 472
Mc mkmquCdMJFzJSNTI 3
yAtgWWWRKgdGC sg 470
yAtgWWWRKgdGC wWzeMpuXdgdjFGrQsUu 984
FjQEfIEiYHknDkDZtNWI iyEFwFBYOwcA 35
iyEFwFBYOwcA Fredericton 668
10 7 12 10 9 10 8 2 0 13 10

17
Calgary
jZUVvhiAs
z
eGQnzAPSaTWauIt
XqHa
yglBqvXk
UMAcWyBu
KNthUN
EsodNCVsXCsw
MEEHZucj
WuP
upujnJxYpthUYr
LF
roMqu
TGguuIlaH
h
Fredericton
76
Calgary eGQnzAPSaTWauIt 245
Calgary yglBqvXk 941
Calgary UMAcWyBu 6
Calgary MEEHZucj 135
Calgary WuP 588
Calgary upujnJxYpthUYr 415
Calgary roMqu 271
Calgary Fredericton 416
jZUVvhiAs z 652
jZUVvhiAs XqHa 453
jZUVvhiAs yglBqvXk 414
jZUVvhiAs WuP 605
jZUVvhiAs upujnJxYpthUYr 362
jZUVvhiAs LF 817
jZUVvhiAs TGguuIlaH 701
jZUVvhiAs h 452
jZUVvhiAs Fredericton 65
z eGQnzAPSaTWauIt 296
z XqHa 852
z UMAcWyBu 278
z EsodNCVsXCsw 205
z upujnJxYpthUYr 515
z LF 692
z roMqu 691
z TGguuIlaH 194
eGQnzAPSaTWauIt yglBqvXk 678
eGQnzAPSaTWauIt UMAcWyBu 687
eGQnzAPSaTWauIt WuP 431
eGQnzAPSaTWauIt roMqu 799
eGQnzAPSaTWauIt TGguuIlaH 338
eGQnzAPSaTWauIt h 557
eGQnzAPSaTWauIt Fredericton 45
XqHa EsodNCVsXCsw 632
XqHa MEEHZucj 915
XqHa WuP 532
XqHa upujnJxYpthUYr 572
XqHa LF 330
XqHa roMqu 155
XqHa h 988
yglBqvXk UMAcWyBu 982
yglBqvXk EsodNCVsXCsw 961
yglBqvXk MEEHZucj 755
yglBqvXk upujnJxYpthUYr 939
yglBqvXk LF 323
yglBqvXk roMqu 572
yglBqvXk h 992
yglBqvXk Fredericton 776
UMAcWyBu MEEHZucj 990
UMAcWyBu WuP 640
UMAcWyBu LF 980
UMAcWyBu TGguuIlaH 268
UMAcWyBu h 845
UMAcWyBu Fredericton 496
KNthUN EsodNCVsXCsw 960
KNthUN LF 537
KNthUN roMqu 690
KNthUN TGguuIlaH 990
KNthUN h 576
EsodNCVsXCsw MEEHZucj 473
EsodNCVsXCsw WuP 142
EsodNCVsXCsw LF 915
EsodNCVsXCsw Fredericton 382
MEEHZucj WuP 539
MEEHZucj upujnJxYpthUYr 899
MEEHZucj TGguuIlaH 298
MEEHZucj h 423
WuP LF 471
WuP roMqu 980
WuP TGguuIlaH 578
upujnJxYpthUYr roMqu 812
upujnJxYpthUYr Fredericton 963
LF roMqu 891
roMqu Fredericton 567
TGguuIlaH h 254
TGguuIlaH Fredericton 215
h Fredericton 491
10 17 13 7 3 11 7 3 11 16 17

2
Calgary
Fredericton
0
10 0 1 1 0 1 1 0 1 2 2

15
Calgary
GTceSLXv
JRzl
zGvMJVNfmTitnRB
bk
YqmXzbGV
QfaIOhTwzEEnHpwTnV
dzAK
cEwMSMxPzTraFmDE
kfzocSPoGLOULiHUCN
DURtYNyzwLogQIM
qCEmJZAuAL
jX
Fw
Fredericton
61
Calgary zGvMJVNfmTitnRB 630
Calgary YqmXzbGV 136
Calgary QfaIOhTwzEEnHpwTnV 447
Calgary kfzocSPoGLOULiHUCN 562
Calgary DURtYNyzwLogQIM 951
Calgary qCEmJZAuAL 572
Calgary jX 829
Calgary Fredericton 606
GTceSLXv zGvMJVNfmTitnRB 35
GTceSLXv bk 156
GTceSLXv dzAK 635
GTceSLXv kfzocSPoGLOULiHUCN 634
GTceSLXv jX 83
GTceSLXv Fredericton 880
JRzl bk 454
JRzl YqmXzbGV 350
JRzl QfaIOhTwzEEnHpwTnV 590
JRzl dzAK 363
JRzl cEwMSMxPzTraFmDE 414
JRzl qCEmJZAuAL 455
JRzl jX 347
JRzl Fredericton 643
zGvMJVNfmTitnRB YqmXzbGV 737
zGvMJVNfmTitnRB dzAK 917
zGvMJVNfmTitnRB qCEmJZAuAL 620
zGvMJVNfmTitnRB jX 913
zGvMJVNfmTitnRB Fredericton 962
bk cEwMSMxPzTraFmDE 434
bk DURtYNyzwLogQIM 626
bk qCEmJZAuAL 78
YqmXzbGV QfaIOhTwzEEnHpwTnV 671
YqmXzbGV dzAK 256
YqmXzbGV cEwMSMxPzTraFmDE 566
YqmXzbGV kfzocSPoGLOULiHUCN 119
YqmXzbGV DURtYNyzwLogQIM 818
YqmXzbGV qCEmJZAuAL 517
YqmXzbGV Fredericton 43
QfaIOhTwzEEnHpwTnV dzAK 999
QfaIOhTwzEEnHpwTnV kfzocSPoGLOULiHUCN 124
QfaIOhTwzEEnHpwTnV DURtYNyzwLogQIM 78
QfaIOhTwzEEnHpwTnV jX 156
QfaIOhTwzEEnHpwTnV Fw 759
dzAK kfzocSPoGLOULiHUCN 64
dzAK qCEmJZAuAL 591
dzAK jX 991
dzAK Fw 518
dzAK Fredericton 942
cEwMSMxPzTraFmDE DURtYNyzwLogQIM 933
cEwMSMxPzTraFmDE qCEmJZAuAL 233
cEwMSMxPzTraFmDE jX 356
cEwMSMxPzTraFmDE Fw 388
cEwMSMxPzTraFmDE Fredericton 932
kfzocSPoGLOULiHUCN DURtYNyzwLogQIM 352
kfzocSPoGLOULiHUCN qCEmJZAuAL 478
kfzocSPoGLOULiHUCN Fw 849
DURtYNyzwLogQIM qCEmJZAuAL 972
DURtYNyzwLogQIM Fredericton 391
qCEmJZAuAL Fw 811
qCEmJZAuAL Fredericton 758
jX Fw 18
Fw Fredericton 242
1 10

13
Calgary
nicSyUmwAk
fYqfs
omcRiygrPh
tKUdKdXTn
b
jBIaNKgpUXrtz
NeSZhKSPOiTXD
puKcX
gopazdOTqgoaKq
umQ
YAxJDYdZI
Fredericton
39
Calgary nicSyUmwAk 317
Calgary fYqfs 836
Calgary b 977
Calgary puKcX 327
Calgary YAxJDYdZI 235
Calgary Fredericton 402
nicSyUmwAk omcRiygrPh 268
nicSyUmwAk b 53
nicSyUmwAk jBIaNKgpUXrtz 200
nicSyUmwAk NeSZhKSPOiTXD 828
nicSyUmwAk puKcX 378
nicSyUmwAk Fredericton 386
fYqfs tKUdKdXTn 792
fYqfs b 329
fYqfs gopazdOTqgoaKq 925
fYqfs umQ 927
omcRiygrPh tKUdKdXTn 359
omcRiygrPh jBIaNKgpUXrtz 731
omcRiygrPh NeSZhKSPOiTXD 931
omcRiygrPh gopazdOTqgoaKq 338
omcRiygrPh umQ 84
tKUdKdXTn b 804
tKUdKdXTn jBIaNKgpUXrtz 468
tKUdKdXTn puKcX 318
tKUdKdXTn umQ 673
tKUdKdXTn YAxJDYdZI 846
tKUdKdXTn Fredericton 682
b jBIaNKgpUXrtz 439
b NeSZhKSPOiTXD 647
b puKcX 875
b gopazdOTqgoaKq 621
jBIaNKgpUXrtz umQ 316
jBIaNKgpUXrtz YAxJDYdZI 63
NeSZhKSPOiTXD puKcX 598
NeSZhKSPOiTXD YAxJDYdZI 643
NeSZhKSPOiTXD Fredericton 298
puKcX Fredericton 352
gopazdOTqgoaKq YAxJDYdZI 263
umQ Fredericton 704
5 9 10 2 2 13

11
Calgary
moiyLuAtMYBBXXuW
M
bxHRbFAGDveXXKH
IHyOd
rQ
TBNsUaxQRezZxWFdg
wqwnDuIrTakwVpc
youZztZFg
GsRzNEbcxpyrdrMiuY
Fredericton
30
Calgary moiyLuAtMYBBXXuW 570
Calgary IHyOd 343
Calgary rQ 34
Calgary youZztZFg 502
Calgary GsRzNEbcxpyrdrMiuY 505
moiyLuAtMYBBXXuW M 817
moiyLuAtMYBBXXuW IHyOd 255
moiyLuAtMYBBXXuW wqwnDuIrTakwVpc 33
moiyLuAtMYBBXXuW GsRzNEbcxpyrdrMiuY 517
moiyLuAtMYBBXXuW Fredericton 239
M bxHRbFAGDveXXKH 61
M youZztZFg 956
M Fredericton 755
bxHRbFAGDveXXKH TBNsUaxQRezZxWFdg 370
bxHRbFAGDveXXKH wqwnDuIrTakwVpc 520
bxHRbFAGDveXXKH youZztZFg 490
bxHRbFAGDveXXKH GsRzNEbcxpyrdrMiuY 872
bxHRbFAGDveXXKH Fredericton 385
IHyOd TBNsUaxQRezZxWFdg 783
IHyOd youZztZFg 286
IHyOd Fredericton 472
rQ TBNsUaxQRezZxWFdg 630
rQ wqwnDuIrTakwVpc 918
rQ youZztZFg 420
rQ Fredericton 188
TBNsUaxQRezZxWFdg wqwnDuIrTakwVpc 984
TBNsUaxQRezZxWFdg youZztZFg 500
wqwnDuIrTakwVpc GsRzNEbcxpyrdrMiuY 101
youZztZFg Fredericton 637
GsRzNEbcxpyrdrMiuY Fredericton 69
9 11 1 4 5 2 1 4 3 2

5
Calgary
cdYFsx
kUfdDZyBh
SiLKBpTq
Fredericton
8
Calgary cdYFsx 754
Calgary SiLKBpTq 712
Calgary Fredericton 974
cdYFsx kUfdDZyBh 140
cdYFsx Fredericton 759
kUfdDZyBh SiLKBpTq 322
kUfdDZyBh Fredericton 613
SiLKBpTq Fredericton 937
8 4 5 5 3 2 4 2 2

16
Calgary
hJynp
cXGLoEHyoc
WrhPqb
alTEhZWrB
wXm
cigIWVbpHrnPQKjAh
nXPcchnZJfjj
h
oplnRUXbxztg
RTvpJbKRXaqZ
hSThwBX
vCvjLWWuEeadE
vb
rNyJ
Fredericton
54
Calgary hJynp 78
Calgary WrhPqb 824
Calgary alTEhZWrB 316
Calgary wXm 759
Calgary cigIWVbpHrnPQKjAh 89
Calgary nXPcchnZJfjj 430
Calgary rNyJ 781
hJynp nXPcchnZJfjj 717
hJynp vCvjLWWuEeadE 408
hJynp vb 980
hJynp rNyJ 897
hJynp Fredericton 264
cXGLoEHyoc WrhPqb 1
cXGLoEHyoc cigIWVbpHrnPQKjAh 323
cXGLoEHyoc nXPcchnZJfjj 838
cXGLoEHyoc RTvpJbKRXaqZ 336
cXGLoEHyoc hSThwBX 673
cXGLoEHyoc vb 688
cXGLoEHyoc rNyJ 120
WrhPqb wXm 101
WrhPqb cigIWVbpHrnPQKjAh 816
WrhPqb oplnRUXbxztg 510
WrhPqb vb 807
alTEhZWrB nXPcchnZJfjj 66
alTEhZWrB h 879
alTEhZWrB oplnRUXbxztg 147
alTEhZWrB rNyJ 708
alTEhZWrB Fredericton 625
wXm vCvjLWWuEeadE 794
wXm vb 739
wXm Fredericton 114
cigIWVbpHrnPQKjAh oplnRUXbxztg 224
cigIWVbpHrnPQKjAh hSThwBX 915
cigIWVbpHrnPQKjAh vCvjLWWuEeadE 782
cigIWVbpHrnPQKjAh Fredericton 983
nXPcchnZJfjj RTvpJbKRXaqZ 356
nXPcchnZJfjj hSThwBX 212
nXPcchnZJfjj vb 116
nXPcchnZJfjj rNyJ 74
h oplnRUXbxztg 620
h RTvpJbKRXaqZ 97
h Fredericton 971
oplnRUXbxztg vCvjLWWuEeadE 237
oplnRUXbxztg vb 450
oplnRUXbxztg rNyJ 646
oplnRUXbxztg Fredericton 427
RTvpJbKRXaqZ vb 139
RTvpJbKRXaqZ rNyJ 320
hSThwBX Fredericton 467
vCvjLWWuEeadE vb 259
vCvjLWWuEeadE Fredericton 773
vb rNyJ 283
vb Fredericton 769
rNyJ Fredericton 932
2 0 11

10
Calgary
zAZMBlYtpPdcYZcfELq
SeXPMpQqPvKlNbLMyBp
EoZIvQCnmtVVVEFS
GILIsFZGtgLJqGW
efFAdoleHBiGCRjrcgjr
HE
bmBqIvmI
lCNmEnp
Fredericton
26
Calgary zAZMBlYtpPdcYZcfELq 405
Calgary SeXPMpQqPvKlNbLMyBp 677
Calgary EoZIvQCnmtVVVEFS 460
Calgary GILIsFZGtgLJqGW 761
Calgary efFAdoleHBiGCRjrcgjr 706
Calgary lCNmEnp 986
zAZMBlYtpPdcYZcfELq SeXPMpQqPvKlNbLMyBp 758
zAZMBlYtpPdcYZcfELq efFAdoleHBiGCRjrcgjr 87
zAZMBlYtpPdcYZcfELq bmBqIvmI 96
zAZMBlYtpPdcYZcfELq lCNmEnp 363
zAZMBlYtpPdcYZcfELq Fredericton 103
SeXPMpQqPvKlNbLMyBp GILIsFZGtgLJqGW 945
SeXPMpQqPvKlNbLMyBp efFAdoleHBiGCRjrcgjr 919
SeXPMpQqPvKlNbLMyBp HE 577
SeXPMpQqPvKlNbLMyBp Fredericton 116
EoZIvQCnmtVVVEFS bmBqIvmI 943
EoZIvQCnmtVVVEFS lCNmEnp 7
EoZIvQCnmtVVVEFS Fredericton 962
GILIsFZGtgLJqGW bmBqIvmI 286
GILIsFZGtgLJqGW lCNmEnp 992
efFAdoleHBiGCRjrcgjr bmBqIvmI 772
efFAdoleHBiGCRjrcgjr Fredericton 428
HE bmBqIvmI 481
HE lCNmEnp 254
HE Fredericton 23
lCNmEnp Fredericton 396
10 8 1 9 7 1 5 4 9 2 7

15
Calgary
ISFdqycX
kdamkqNtvXQpvE
rjtgqi
TtKAqHuHIsushQY
tTwmcpZ
AeYtzghNCBYzsxdX
COqcoaHYkhNSmuTSx
p
izBVsPIquWGQNLfQ
QLW
es
keKyNPnM
BllcFEtjSU
Fredericton
55
Calgary ISFdqycX 482
Calgary TtKAqHuHIsushQY 574
Calgary tTwmcpZ 33
Calgary AeYtzghNCBYzsxdX 152
Calgary izBVsPIquWGQNLfQ 515
Calgary QLW 191
Calgary es 588
ISFdqycX rjtgqi 394
ISFdqycX tTwmcpZ 763
ISFdqycX AeYtzghNCBYzsxdX 592
ISFdqycX COqcoaHYkhNSmuTSx 483
ISFdqycX es 540
ISFdqycX BllcFEtjSU 350
ISFdqycX Fredericton 981
kdamkqNtvXQpvE AeYtzghNCBYzsxdX 622
kdamkqNtvXQpvE COqcoaHYkhNSmuTSx 480
kdamkqNtvXQpvE izBVsPIquWGQNLfQ 668
kdamkqNtvXQpvE keKyNPnM 765
rjtgqi tTwmcpZ 467
rjtgqi AeYtzghNCBYzsxdX 916
rjtgqi COqcoaHYkhNSmuTSx 115
rjtgqi izBVsPIquWGQNLfQ 231
rjtgqi QLW 730
rjtgqi es 450
rjtgqi keKyNPnM 159
rjtgqi Fredericton 246
TtKAqHuHIsushQY COqcoaHYkhNSmuTSx 492
TtKAqHuHIsushQY QLW 353
TtKAqHuHIsushQY es 103
TtKAqHuHIsushQY keKyNPnM 752
TtKAqHuHIsushQY BllcFEtjSU 528
TtKAqHuHIsushQY Fredericton 585
tTwmcpZ AeYtzghNCBYzsxdX 327
tTwmcpZ QLW 561
tTwmcpZ es 90
tTwmcpZ Fredericton 194
AeYtzghNCBYzsxdX p 104
AeYtzghNCBYzsxdX izBVsPIquWGQNLfQ 30
AeYtzghNCBYzsxdX QLW 589
AeYtzghNCBYzsxdX keKyNPnM 868
AeYtzghNCBYzsxdX Fredericton 622
COqcoaHYkhNSmuTSx izBVsPIquWGQNLfQ 424
COqcoaHYkhNSmuTSx es 760
COqcoaHYkhNSmuTSx keKyNPnM 972
p izBVsPIquWGQNLfQ 406
p es 382
izBVsPIquWGQNLfQ QLW 453
izBVsPIquWGQNLfQ es 426
izBVsPIquWGQNLfQ BllcFEtjSU 499
izBVsPIquWGQNLfQ Fredericton 272
QLW BllcFEtjSU 694
es BllcFEtjSU 966
es Fredericton 855
keKyNPnM BllcFEtjSU 425
BllcFEtjSU Fredericton 417
5 15 5 7 7 5
AC output:

Code: Select all

Scenario #1
Total cost of flight(s) is $484
Total cost of flight(s) is $484
Total cost of flight(s) is $484
Total cost of flight(s) is $484
Total cost of flight(s) is $484
Total cost of flight(s) is $484
Total cost of flight(s) is $484
Total cost of flight(s) is $484
Total cost of flight(s) is $484
Total cost of flight(s) is $484

Scenario #2
Total cost of flight(s) is $290
Total cost of flight(s) is $290
Total cost of flight(s) is $290
Total cost of flight(s) is $290
Total cost of flight(s) is $290
Total cost of flight(s) is $290
Total cost of flight(s) is $290
Total cost of flight(s) is $290
Total cost of flight(s) is $290
Total cost of flight(s) is $290

Scenario #3
No satisfactory flights
No satisfactory flights
No satisfactory flights
No satisfactory flights
No satisfactory flights
No satisfactory flights
No satisfactory flights
No satisfactory flights
No satisfactory flights
No satisfactory flights

Scenario #4
Total cost of flight(s) is $179

Scenario #5
Total cost of flight(s) is $402
Total cost of flight(s) is $402
Total cost of flight(s) is $402
Total cost of flight(s) is $402
Total cost of flight(s) is $402

Scenario #6
Total cost of flight(s) is $222
Total cost of flight(s) is $222
Total cost of flight(s) is $222
Total cost of flight(s) is $222
Total cost of flight(s) is $222
Total cost of flight(s) is $222
Total cost of flight(s) is $222
Total cost of flight(s) is $222
Total cost of flight(s) is $222

Scenario #7
Total cost of flight(s) is $974
Total cost of flight(s) is $974
Total cost of flight(s) is $974
Total cost of flight(s) is $974
Total cost of flight(s) is $974
Total cost of flight(s) is $974
Total cost of flight(s) is $974
Total cost of flight(s) is $974

Scenario #8
No satisfactory flights
Total cost of flight(s) is $342

Scenario #9
Total cost of flight(s) is $508
Total cost of flight(s) is $508
Total cost of flight(s) is $508
Total cost of flight(s) is $508
Total cost of flight(s) is $508
Total cost of flight(s) is $508
Total cost of flight(s) is $508
Total cost of flight(s) is $508
Total cost of flight(s) is $508
Total cost of flight(s) is $508

Scenario #10
Total cost of flight(s) is $227
Total cost of flight(s) is $227
Total cost of flight(s) is $227
Total cost of flight(s) is $227
Total cost of flight(s) is $227
Check input and AC output for thousands of problems on uDebug!

lehuyduc
New poster
Posts: 5
Joined: Tue Dec 02, 2014 6:03 pm

Re: 11280 - Flying to Fredericton

Post by lehuyduc » Tue Jan 06, 2015 3:09 pm

Can you tell me on which test case my program fail please ? Thanks.

Code: Select all

/*
ID: lehuydu1
PROG:
LANG: C++
*/

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

#define x first
#define y second
typedef long long ll;
typedef double rl;
typedef pair<int,int> pt;
int dx[5]={0,0,0,1,-1},
    dy[5]={0,1,-1,0,0};
const ll base = ll(1000000007)*ll(1000000);

int n,m,Q,Test;
ll res[202][202]; // res[i][j] minimum cost to travel to i
                  // using at most j flights
vector <pt> a[102]; // store edges .x is cost and .y is vertex
map <string,int> mp; // store cities

void solve(int tt)
{
    int i,j,k,u,v,t;
    string s1,s2;

    cin >> n;
    for (i=1;i<=n;i++)
    {
        cin >> s1;
        mp[s1] = i;
        res[i][0] = base;
    }
    res[1][0] = 0;

    cin >> m;
    for (i=1;i<=m;i++)
    {
        cin >> s1 >> s2 >> k;
        a[mp[s2]].push_back(pt(k,mp[s1]));
    }

    // DP: res[v][t] = min(res[v][t-1] , res[u][t-1] + cost[u][v])
    for (t=1;t<=n;t++)
        for (v=1;v<=n;v++)
        {
            res[v][t] = res[v][t-1];
            for (i=0;i<a[v].size();i++)
            {
                u = a[v][i].y;
                res[v][t] = min(res[v][t],res[u][t-1] + a[v][i].x);
            }
        }


    cout << "Scenario #" << tt << "\n";
    cin >> Q;
    for (i=1;i<=Q;i++)
    {
        cin >> t;
        t++; t = min(t,n);
        if (res[n][t]!=base)
            cout << "Total cost of flight(s) is $" << res[n][t];
        else
            cout << "No satisfactory flights";
        if (i!=Q) cout << "\n";
    }
    if (tt!=Test) cout << "\n\n";

    // reset everything
    mp.clear();
    for (i=1;i<=n;i++) a[i].clear();
}

int main()
{
    int i,t;
    //freopen("uva11280.inp","r",stdin);
 //   freopen("uva11280.out","w",stdout);

    cin >> Test;
    for (i=1;i<=Test;i++) solve(i);
    return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11280 - Flying to Fredericton

Post by brianfry713 » Wed Jan 07, 2015 3:06 am

Always print a newline char at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

lehuyduc
New poster
Posts: 5
Joined: Tue Dec 02, 2014 6:03 pm

Re: 11280 - Flying to Fredericton

Post by lehuyduc » Wed Jan 07, 2015 3:45 pm

Didn't know that was necessary o_O . Thanks a lot

double_zero
New poster
Posts: 8
Joined: Sat Jun 28, 2014 12:42 pm

Re: 11280 - Flying to Fredericton

Post by double_zero » Tue Jan 27, 2015 10:34 am

Keep Getting WA, But My Code Work's Fine With Every Test Case That's in here.

Could anyone help me by giving a Test case that breaks my Code? or tell me whats Wrong With My Code?

Code: Select all

#include <iostream>
#include <math.h>
#include <algorithm>
#include <fstream>
#include <string>
#include <map>
#define INF (int)1e9

using namespace std;

int cost[110][110], dp[110][110], n, m;

int solve(int i , int q){
	int ans=INF;
	if(i==0) return 0;
	if(q<0) return INF;
	if(dp[i][q]!=-1) return dp[i][q];
	for(int j=0 ; j<n ; j++){
		if(cost[j][i]!=INF)
			ans=min(ans, solve(j,q-1)+cost[j][i]);
	}
	return dp[i][q]=ans;
}

map<string, int> mp;

int main(){
	int tc,t=1; cin >> tc; 
	while(tc--){
		cin >> n; mp.clear();
		for(int i=0 ; i<110 ; i++)
			for(int j=0 ;  j<110 ;j++)
				cost[i][j]=INF, dp[i][j]=-1;
		string tmp; 
		for(int i=0 ; i<n ; i++){
			cin >> tmp; mp[tmp]=i;
		}
		cin >> m;
		string tmp1, tmp2; int c;
		for(int i=0 ; i<m ; i++){
			cin >> tmp1 >> tmp2 >> c;
			cost[mp[tmp1]][mp[tmp2]]=c;
		}
		int qn; cin >> qn;
		cout << "Scenario #" << t++ << endl;
		for(int i=0 ; i<qn ; i++){
			int q; cin >> q; if(q) q=((q%n)?(q%n):n);
			int ans=solve(n-1, q);
			if(ans>=INF) cout << "No satisfactory flights" << endl;
			else cout << "Total cost of flight(s) is $" << ans << endl;
		}
		if(tc!=0) cout << endl;
	}
	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11280 - Flying to Fredericton

Post by brianfry713 » Tue Jan 27, 2015 9:37 pm

Describe your code. You can solve this using Bellman-Ford's algorithm.
Check input and AC output for thousands of problems on uDebug!

double_zero
New poster
Posts: 8
Joined: Sat Jun 28, 2014 12:42 pm

Re: 11280 - Flying to Fredericton

Post by double_zero » Thu Jan 29, 2015 9:38 pm

I use a simple dp.

dp[q]=min(dp[j][q-1]+cost[j]) for all j that i is a neighbor of j. (cost[j]!=INF)

(i==current city, j==previous city, q==remaining stopovers).

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11280 - Flying to Fredericton

Post by brianfry713 » Fri Jan 30, 2015 2:23 am

Input:

Code: Select all

1

2
Calgary
Fredericton
2
Calgary Fredericton 1
Calgary Fredericton 2
1 0
AC output:

Code: Select all

Scenario #1
Total cost of flight(s) is $1
Check input and AC output for thousands of problems on uDebug!

double_zero
New poster
Posts: 8
Joined: Sat Jun 28, 2014 12:42 pm

Re: 11280 - Flying to Fredericton

Post by double_zero » Fri Jan 30, 2015 11:53 am

Thank you brianfry713. ;)

coder21
New poster
Posts: 5
Joined: Tue Feb 10, 2015 9:13 am

11280 - Flying to Fredericton

Post by coder21 » Thu Sep 03, 2015 7:10 am

I have tried all available inputs here and also in udebug but still getting WAs in online judge.
Can someone please take a look at my code.
Thank you.

Code: Select all

#include<stdio.h>
#define VALUE 1000000000

long long dist[1001];
char cityNames[102][41];
int adjList[102][1001];
int indexCity;
int listIndex;
int selected[1001];

struct City
{
	int end;	
	long long cost;
};

City cities[1001];


void reset(int n)
{
	for(int i=0;i<n;i++)
	{	
		for(int j=0;j<n;j++)
		{
			adjList[i][j] = 0;
		}
	}
}

void refill(int n)
{
	for(int i=0;i<n;i++)
	{
		dist[i]=VALUE;		
		selected[i]=0;
	}
}

int findCity(char str[], int N)
{
	int i,j;
	bool flag;
	for(i=0;i<N;i++)
	{
		j=0;
		flag = false;
		while(str[j]==cityNames[i][j])
		{
			j++;
			if(str[j]==0 && cityNames[i][j]==0)
				{flag = true;break;}
		}

		if(flag)
			break;
	}

	return i;
}


int minDistance(int N)
{   
	long long min = VALUE;
	int min_index;
 
   for (int v = 0; v < N; v++)
	   if (selected[v] == 0 && dist[v] <= min)
         min = dist[v], min_index = v;
 
   return min_index;
}

long long dijkstra1(int N, int limit)
{              
    long long distance;
	int strIndex,v; 
	dist[0] = 0;
 
     // Find shortest path for all vertices
     for (int count = 0; count < N; count++)
     {
		 if(count==limit+1)break;
       // Pick the minimum distance vertex from the set of vertices not
       // yet processed. u is always equal to src in first iteration.
       int u = minDistance(N);        
	   selected[u]=1;
        
	   for(int i=1; i <= adjList[u][0]; i++)
        {
			strIndex = adjList[u][i];
			distance = dist[u] +  cities[strIndex].cost ;
			v = cities[strIndex].end;

			if (!selected[v] && dist[u] != VALUE && distance < dist[v])
				dist[v] = distance;
	   }	   	   
     }
      
	 return dist[N-1];
}

int main()
{
	freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int T,tc=0,N,M,q,stoppage;
	long long cost;

	scanf("%d",&T);

	while(T--)
	{
		tc++;
		if(tc>1)
			printf("\n");
		indexCity=0;
		listIndex=0;
		scanf("%d ",&N);
		reset(N);

		int i=0;
		while(i<N)
		{
			gets(cityNames[i]);
			i++;
		}

		scanf("%d ",&M);

		int x,y;
		char city1[41], city2[41];
		i=0;
		while(i<M)
		{
			scanf("%s %s %lld ",&city1, &city2, &cost);						
			x = findCity(city1, N);
			y = findCity(city2, N);

			adjList[x][0] = adjList[x][0] +1;			
			cities[indexCity].end = y;
			cities[indexCity].cost = cost;
			int column = adjList[x][0];
			adjList[x][column] = indexCity++;
		
			i++;
		}

		
		printf("Scenario #%d\n",tc);
		scanf("%d ", &q);
		long long val;
		for(int j=0;j<q;j++)
		{
			scanf("%d ",&stoppage);
			refill(N);
			val = dijkstra1(N, stoppage);
			if(val!=VALUE)
				printf("Total cost of flight(s) is $%lld\n",val);
			else
				printf("No satisfactory flights\n");
		}

	}

	return 0;
}
Last edited by brianfry713 on Tue Sep 08, 2015 1:10 am, edited 1 time in total.
Reason: Added code block

Post Reply

Return to “Volume 112 (11200-11299)”