UVa10075 - Airlines(所有点对之间的最短距离)

#include <cstdio>#include <map>#include <string>#include <cmath>#include <algorithm>usingnamespacestd;
constintN=110, INF=0x3f3f3f3f;
constintSTRLEN=25;
constdoublePI=acos(-1);
constintR=6378;
structLocation{
doublelati, longti;
};
Locationlocation[N];
intf[N][N];
intn, m, q;
map<string, int>strMap;
intt;
boolinput();
voidsolve();
intdis(inta, intb);
intmain()
{
#ifndef ONLINE_JUDGEfreopen("d:\\OJ\\uva_in.txt", "r", stdin);
#endif // ONLINE_JUDGEt=1;
while (input()) {
solve();
    }
return0;
}
boolinput()
{
strMap.clear();
scanf("%d%d%d", &n, &m, &q);
if (n==0&&m==0&&q==0) returnfalse;
charbuf[STRLEN];
for (inti=0; i<n; i++) {
scanf("%s%lf%lf", buf, &location[i].lati, &location[i].longti);
stringstr=buf;
strMap[str] =i;
    }
for (inti=0; i<n; i++) {
for (intj=0; j<n; j++) {
if (i==j) f[i][j] =0;
elsef[i][j] =INF;
        }
    }
for (inti=0; i<m; i++) {
scanf("%s", buf);
strings=buf;
intu=strMap[s];
scanf("%s", buf);
s=buf;
intv=strMap[s];
f[u][v] =dis(u, v);
    }
returntrue;
}
intdis(inta, intb)
{
doublealpha=location[a].lati/180*PI;
doublebelta=location[a].longti/180*PI;
doublez1=R*sin(alpha);
doublex1=R*cos(alpha) *cos(belta);
doubley1=R*cos(alpha) *sin(belta);
alpha=location[b].lati/180*PI;
belta=location[b].longti/180*PI;
doublez2=R*sin(alpha);
doublex2=R*cos(alpha) *cos(belta);
doubley2=R*cos(alpha) *sin(belta);
doubletheta=acos((x1*x2+y1*y2+z1*z2) /R/R);
return (int)round(R*theta);
}
voidsolve()
{
for (intk=0; k<n; k++) {
for (inti=0; i<n; i++) {
for (intj=0; j<n; j++) {
if (f[i][k] !=INF&&f[k][j] !=INF) {
f[i][j] =min(f[i][j], f[i][k] +f[k][j]);
                }
            }
        }
    }
if (t>1) printf("\n");
printf("Case #%d\n", t++);
for (inti=0; i<q; i++) {
charbuf1[STRLEN], buf2[STRLEN];
scanf("%s%s", buf1, buf2);
strings1=buf1, s2=buf2;
intu=strMap[s1], v=strMap[s2];
if (f[u][v] !=INF) {
printf("%d km\n", f[u][v]);
        } else {
printf("no route exists\n");
        }
    }
}