#define R 3390.0
#define versine(x) (1-cos(x))
#define haversine(x) ( (1 - cos(x))/2 )
#define RND(x) ( int(floor(x+0.5)) )
struct point
{
string name;
double lat;
double lon;
};
point points[100];
int numpoints;
long long distances[100][100];
bool visited[100];
long long dis[100];
int parent[100];
double dist(point p1, point p2)
{
double a = haversine(p2.lat - p1.lat);
double b = cos(p1.lat) * cos(p2.lat) * haversine(p2.lon - p1.lon);
double c = 2 * atan2(sqrt(a + b), sqrt(1 - a - b));
return R * c;
}
int getindex(string name)
{
for(int i = 0; i < numpoints; i++)
{
if(points[i].name == name) return i;
}
return 0;
}
bool dj(int start, int end, int range)
{
for(int i = 0; i < numpoints; i++)
{
visited[i] = false;
dis[i] = 1e10;
parent[i] = -1;
}
dis[start] = 0;
int v = start;
while(!visited[v])
{
visited[v] = true;
for(int i = 0; i < numpoints; i++)
{
if(i == v) continue;
if(dis[v] + distances[v][i] < dis[i] && distances[v][i] <= range){
dis[i] = dis[v] + distances[v][i];
parent[i] = v;
}
}
v = start;
long long best = 1e9;
for(int i = 0; i < numpoints; i++)
{
if(!visited[i] && dis[i] < best) { best = dis[i]; v = i;}
}
}
if(visited[end]) return true;
return false;
}
void main()
{
int caseno = 1;
while(cin >> numpoints && numpoints)
{
for(int i = 0; i < numpoints; i++)
cin >> points[i].name >> points[i].lat >> points[i].lon;
set<long long> ranges;
for(int i = 0; i < numpoints; i++)
{
for(int j = 0; j < numpoints; j++){
if(i==j) distances[i][j] = 0;
else distances[i][j] = RND(dist(points[i], points[j]));
ranges.insert(distances[i][j]);
}
}
int num;
cin >> num;
cout << "Scenario " << caseno++ << ":" << endl;
for(int n = 0; n < num; n++)
{
for(int i = 0; i < 30; i++) cout << '-';
cout << endl;
string n1, n2;
int lastrange;
cin >> n1 >> n2 >> lastrange;
cout << "From " << n1 << " to " << n2 << " with range " << lastrange << " km:" << endl;
int start = getindex(n1);
int end = getindex(n2);
if(dj(start, end, lastrange))
{
stack<string> res;
while(end != -1)
{
char s[200];
sprintf(s, "%s at %d km.", points[end].name.c_str(), RND(dis[end]));
res.push(s);
end = parent[end];
}
while(res.size()){
cout << res.top() << endl;
res.pop();
}
continue;
}
for(set<long long>::iterator it = ranges.begin(); it != ranges.end(); it++)
{
if(*it <= lastrange) continue;
if(dj(start, end, *it))
{
cout << "No route for this range, minimum required range is " << *it << " km." << endl;
break;
}
}
}
for(int i = 0; i < 30; i++) cout << '-';
cout << endl << endl;
}
}
whenever I get the distance between 2 points, I round it as described in the problem statement and insert it in a set. if the given range is too small, i test all numbers > range from the set. i still get a WA.
100
aa -0.189153 2.263902
ab -0.502504 3.446408
ac -0.583654 1.644747
ad -0.423869 3.753228
ae -0.335398 0.309623
af 0.287535 3.588060
ag -1.194601 4.403616
ah -1.451011 6.046235
ai -0.130068 4.715645
aj 1.161973 4.649513
ak 1.364194 2.713541
al -0.740005 3.985211
am -1.067198 5.045563
an 1.171359 0.527040
ao -0.823473 5.940518
ap 0.458142 5.755036
aq 1.466770 3.782399
ar 0.518147 1.593168
as 1.163586 5.488053
at -1.539609 3.225792
au -1.140367 4.603380
av 1.001401 2.652928
aw -0.219390 6.040466
ax 1.226232 0.452762
ay 0.737986 3.477165
az 0.588494 1.834589
ba -0.483454 5.390744
bb -1.049183 2.109612
bc -1.081925 4.273847
bd -0.970387 0.335801
be -0.243626 2.240933
bf 1.118331 3.130940
bg -0.030631 2.729670
bh 0.992538 3.534030
bi -0.123245 3.874345
bj -0.133975 0.712136
bk -0.154915 5.643882
bl -0.275772 4.740986
bm 1.261694 4.970774
bn -1.553254 5.120495
bo -0.636469 4.209758
bp -1.416348 1.262144
bq 0.606894 1.715864
br 0.471573 3.934748
bs 1.517351 3.373139
bt 0.165478 0.373875
bu -0.313928 0.558963
bv -0.946284 1.704680
bw 0.393331 2.570277
bx 0.733131 2.978490
by -0.389917 5.711349
bz -1.539769 3.746331
ca -0.251774 2.066887
cb 0.796927 3.004584
cc 0.923225 3.752135
cd 1.319334 1.014412
ce 1.082975 5.211740
cf -0.415467 6.007494
cg 0.379509 3.741938
ch 0.726579 0.180630
ci -0.961663 5.102687
cj 1.271755 3.833457
ck 0.217416 4.407608
cl 0.414030 0.579286
cm -0.834366 2.669657
cn 0.153254 2.359818
co 1.355859 1.043977
cp -0.517743 5.234845
cq 0.488615 5.269329
cr -0.339593 2.837575
cs 0.399971 6.010504
ct 0.625429 0.924591
cu -0.323006 5.465950
cv -0.271343 4.834511
cw 0.487616 2.790750
cx 1.060555 3.899471
cy -0.403355 5.979640
cz -0.234824 4.021299
da 0.297394 1.554005
db 0.206524 2.216092
dc 0.680288 1.180362
dd 0.035536 3.082809
de 0.868340 2.571546
df -0.033472 2.912417
dg -0.986760 3.838672
dh 0.630315 0.447165
di 1.516474 1.974681
dj 0.963331 3.822587
dk 0.639527 1.099684
dl -0.047238 3.902030
dm -1.210730 1.545412
dn 0.517909 3.690481
do -0.422940 3.179628
dp -1.130834 2.920292
dq 0.209773 3.401835
dr 1.014761 5.920812
ds 0.546476 2.147336
dt 1.569060 2.524611
du 1.450274 1.933260
dv -1.385875 2.585958
100
aa aa 1253
aa ab 1253
aa ac 1253
aa ad 1253
aa ae 1253
aa af 1253
aa ag 1253
aa ah 1253
aa ai 1253
aa aj 1253
aa ak 1253
aa al 1253
aa am 1253
aa an 1253
aa ao 1253
aa ap 1253
aa aq 1253
aa ar 1253
aa as 1253
aa at 1253
aa au 1253
aa av 1253
aa aw 1253
aa ax 1253
aa ay 1253
aa az 1253
aa ba 1253
aa bb 1253
aa bc 1253
aa bd 1253
aa be 1253
aa bf 1253
aa bg 1253
aa bh 1253
aa bi 1253
aa bj 1253
aa bk 1253
aa bl 1253
aa bm 1253
aa bn 1253
aa bo 1253
aa bp 1253
aa bq 1253
aa br 1253
aa bs 1253
aa bt 1253
aa bu 1253
aa bv 1253
aa bw 1253
aa bx 1253
aa by 1253
aa bz 1253
aa ca 1253
aa cb 1253
aa cc 1253
aa cd 1253
aa ce 1253
aa cf 1253
aa cg 1253
aa ch 1253
aa ci 1253
aa cj 1253
aa ck 1253
aa cl 1253
aa cm 1253
aa cn 1253
aa co 1253
aa cp 1253
aa cq 1253
aa cr 1253
aa cs 1253
aa ct 1253
aa cu 1253
aa cv 1253
aa cw 1253
aa cx 1253
aa cy 1253
aa cz 1253
aa da 1253
aa db 1253
aa dc 1253
aa dd 1253
aa de 1253
aa df 1253
aa dg 1253
aa dh 1253
aa di 1253
aa dj 1253
aa dk 1253
aa dl 1253
aa dm 1253
aa dn 1253
aa do 1253
aa dp 1253
aa dq 1253
aa dr 1253
aa ds 1253
aa dt 1253
aa du 1253
aa dv 1253
0
0
Scenario 1:
------------------------------
From aa to aa with range 1253 km:
No route for this range, minimum required range is 0 km.
------------------------------
From aa to ab with range 1253 km:
aa at 0 km.
cn at 1205 km.
(cutted)
[/size]
Last edited by tadeu on Tue Apr 04, 2006 8:49 pm, edited 2 times in total.
Scenario 1:
------------------------------
From aa to aa with range 1253 km:
aa at 0 km.
------------------------------
From aa to ab with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
------------------------------
From aa to ac with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
ag at 16801 km.
at at 18039 km.
dm at 19275 km.
bv at 20205 km.
ac at 21443 km.
------------------------------
From aa to ad with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
------------------------------
From aa to ae with range 1253 km:
No route for this range, minimum required range is 1528 km.
------------------------------
From aa to af with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
------------------------------
From aa to ag with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
ag at 16801 km.
------------------------------
From aa to ah with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
ag at 16801 km.
bn at 18032 km.
ah at 18405 km.
------------------------------
From aa to ai with range 1253 km:
No route for this range, minimum required range is 1539 km.
------------------------------
From aa to aj with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
cj at 6315 km.
aj at 7312 km.
------------------------------
From aa to ak with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
ak at 6261 km.
------------------------------
From aa to al with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
------------------------------
From aa to am with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
bc at 16506 km.
am at 17728 km.
------------------------------
From aa to an with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
ak at 6261 km.
co at 7317 km.
an at 8118 km.
------------------------------
From aa to ao with range 1253 km:
No route for this range, minimum required range is 1539 km.
------------------------------
From aa to ap with range 1253 km:
No route for this range, minimum required range is 1695 km.
------------------------------
From aa to aq with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
ak at 6261 km.
aq at 6874 km.
------------------------------
From aa to ar with range 1253 km:
aa at 0 km.
cn at 1205 km.
db at 1717 km.
ds at 2889 km.
az at 3793 km.
ar at 4528 km.
------------------------------
From aa to as with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
cj at 6315 km.
bm at 7413 km.
as at 8102 km.
------------------------------
From aa to at with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
ag at 16801 km.
at at 18039 km.
------------------------------
From aa to au with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
bc at 16506 km.
au at 17037 km.
------------------------------
From aa to av with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
av at 5144 km.
------------------------------
From aa to aw with range 1253 km:
No route for this range, minimum required range is 1539 km.
------------------------------
From aa to ax with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
ak at 6261 km.
du at 6761 km.
ax at 7960 km.
------------------------------
From aa to ay with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
------------------------------
From aa to az with range 1253 km:
aa at 0 km.
cn at 1205 km.
db at 1717 km.
ds at 2889 km.
az at 3793 km.
------------------------------
From aa to ba with range 1253 km:
No route for this range, minimum required range is 1539 km.
------------------------------
From aa to bb with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
ag at 16801 km.
at at 18039 km.
dv at 18585 km.
bb at 19827 km.
------------------------------
From aa to bc with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
bc at 16506 km.
------------------------------
From aa to bd with range 1253 km:
No route for this range, minimum required range is 1539 km.
------------------------------
From aa to be with range 1253 km:
aa at 0 km.
be at 200 km.
------------------------------
From aa to bf with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
------------------------------
From aa to bg with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
bg at 10141 km.
------------------------------
From aa to bh with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
bh at 6116 km.
------------------------------
From aa to bi with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
bi at 14636 km.
------------------------------
From aa to bj with range 1253 km:
No route for this range, minimum required range is 1528 km.
------------------------------
From aa to bk with range 1253 km:
No route for this range, minimum required range is 1539 km.
------------------------------
From aa to bl with range 1253 km:
No route for this range, minimum required range is 1539 km.
------------------------------
From aa to bm with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
cj at 6315 km.
bm at 7413 km.
------------------------------
From aa to bn with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
ag at 16801 km.
bn at 18032 km.
------------------------------
From aa to bo with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
bo at 15481 km.
------------------------------
From aa to bp with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
ag at 16801 km.
bn at 18032 km.
bp at 18602 km.
------------------------------
From aa to bq with range 1253 km:
aa at 0 km.
cn at 1205 km.
db at 1717 km.
ds at 2889 km.
bq at 4129 km.
------------------------------
From aa to br with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
br at 6935 km.
------------------------------
From aa to bs with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
ak at 6261 km.
bs at 6829 km.
------------------------------
From aa to bt with range 1253 km:
No route for this range, minimum required range is 1275 km.
------------------------------
From aa to bu with range 1253 km:
No route for this range, minimum required range is 1528 km.
------------------------------
From aa to bv with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
ag at 16801 km.
at at 18039 km.
dm at 19275 km.
bv at 20205 km.
------------------------------
From aa to bw with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
------------------------------
From aa to bx with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
------------------------------
From aa to by with range 1253 km:
No route for this range, minimum required range is 1539 km.
------------------------------
From aa to bz with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
ag at 16801 km.
bz at 17995 km.
------------------------------
From aa to ca with range 1253 km:
aa at 0 km.
ca at 685 km.
------------------------------
From aa to cb with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
------------------------------
From aa to cc with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
cc at 6129 km.
------------------------------
From aa to cd with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
ak at 6261 km.
cd at 7427 km.
------------------------------
From aa to ce with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
cj at 6315 km.
bm at 7413 km.
ce at 8093 km.
------------------------------
From aa to cf with range 1253 km:
No route for this range, minimum required range is 1539 km.
------------------------------
From aa to cg with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
cg at 6685 km.
------------------------------
From aa to ch with range 1253 km:
No route for this range, minimum required range is 1275 km.
------------------------------
From aa to ci with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
bc at 16506 km.
au at 17037 km.
ci at 18059 km.
------------------------------
From aa to cj with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
cj at 6315 km.
------------------------------
From aa to ck with range 1253 km:
No route for this range, minimum required range is 1570 km.
------------------------------
From aa to cl with range 1253 km:
No route for this range, minimum required range is 1275 km.
------------------------------
From aa to cm with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
ag at 16801 km.
at at 18039 km.
dv at 18585 km.
dp at 19506 km.
cm at 20610 km.
------------------------------
From aa to cn with range 1253 km:
aa at 0 km.
cn at 1205 km.
------------------------------
From aa to co with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
ak at 6261 km.
co at 7317 km.
------------------------------
From aa to cp with range 1253 km:
No route for this range, minimum required range is 1539 km.
------------------------------
From aa to cq with range 1253 km:
No route for this range, minimum required range is 1695 km.
------------------------------
From aa to cr with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
------------------------------
From aa to cs with range 1253 km:
No route for this range, minimum required range is 1695 km.
------------------------------
From aa to ct with range 1253 km:
No route for this range, minimum required range is 1275 km.
------------------------------
From aa to cu with range 1253 km:
No route for this range, minimum required range is 1539 km.
------------------------------
From aa to cv with range 1253 km:
No route for this range, minimum required range is 1539 km.
------------------------------
From aa to cw with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
------------------------------
From aa to cx with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
cx at 6523 km.
------------------------------
From aa to cy with range 1253 km:
No route for this range, minimum required range is 1539 km.
------------------------------
From aa to cz with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
cz at 14615 km.
------------------------------
From aa to da with range 1253 km:
aa at 0 km.
cn at 1205 km.
db at 1717 km.
ds at 2889 km.
az at 3793 km.
ar at 4528 km.
da at 5286 km.
------------------------------
From aa to db with range 1253 km:
aa at 0 km.
cn at 1205 km.
db at 1717 km.
------------------------------
From aa to dc with range 1253 km:
No route for this range, minimum required range is 1275 km.
------------------------------
From aa to dd with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
------------------------------
From aa to de with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
de at 5054 km.
------------------------------
From aa to df with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
------------------------------
From aa to dg with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
------------------------------
From aa to dh with range 1253 km:
No route for this range, minimum required range is 1275 km.
------------------------------
From aa to di with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
ak at 6261 km.
di at 6839 km.
------------------------------
From aa to dj with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dj at 6323 km.
------------------------------
From aa to dk with range 1253 km:
No route for this range, minimum required range is 1275 km.
------------------------------
From aa to dl with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
bi at 14636 km.
dl at 14910 km.
------------------------------
From aa to dm with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
ag at 16801 km.
at at 18039 km.
dm at 19275 km.
------------------------------
From aa to dn with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
------------------------------
From aa to do with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
------------------------------
From aa to dp with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
ag at 16801 km.
at at 18039 km.
dv at 18585 km.
dp at 19506 km.
------------------------------
From aa to dq with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
------------------------------
From aa to dr with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
cj at 6315 km.
bm at 7413 km.
as at 8102 km.
dr at 8939 km.
------------------------------
From aa to ds with range 1253 km:
aa at 0 km.
cn at 1205 km.
db at 1717 km.
ds at 2889 km.
------------------------------
From aa to dt with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
ak at 6261 km.
dt at 6956 km.
------------------------------
From aa to du with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
cb at 4211 km.
bf at 5326 km.
ak at 6261 km.
du at 6761 km.
------------------------------
From aa to dv with range 1253 km:
aa at 0 km.
cn at 1205 km.
bw at 2269 km.
cw at 3016 km.
bx at 3996 km.
ay at 5244 km.
dn at 6190 km.
af at 7033 km.
dq at 7699 km.
dd at 8923 km.
df at 9546 km.
cr at 10613 km.
do at 11725 km.
ab at 12577 km.
ad at 13544 km.
al at 14797 km.
dg at 15692 km.
ag at 16801 km.
at at 18039 km.
dv at 18585 km.
------------------------------
Pretty similar, but not identical...
Hope it helps
Last edited by Ivan on Tue Apr 04, 2006 10:17 pm, edited 2 times in total.
Thanks Ivan!
I have already fixed the problem with source==destination, the outputs are identical now, but I am still getting WA!
I'll try to test with more complicated/singular/degenerate cases later..
Tadeu, your first case is invalid because it's given in the description that source and destination are always different; you don't have to take care of that in your program. All other cases would be accepted by the special judge (I ran them against it). One thing: do you print a blank line between scenarios? If not, that can be a cause of WA, not PE, because I think that explicit directions considering the output format should be followed.
If you want, you can PM me your code and I'll check it.
One more thing: I think you better remove the bulky I/O you posted, because it eats away bandwidth from people with not so fast Internet connections.
