URAL/1575

来自"NOCOW"

floyed...

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int station[8]={13,10,11,12,9,14,15,13};
const string line[8][15]={
    {"7_klyuchey","Sortirovochnaya","China_town","Zarechny","City","1905_year_square","Kuybyshevskaya",
        "Sibirskaya","Siniye_kamni","Lechebnaya","Varshavskaya","Kompressornaya","Koltsovo"},
    {"Zelyony_ostrov","Tatishchevskaya","Verh_Isetskaya","Kommunarov_square","1905_year_square",
        "Teatralnaya","Vostochnaya","Vtuzgorodok","Kamennye_palatki","University"},
    {"MEGA","Metallurgov","Kraulya","Central_stadium","Moskovskaya","1905_year_square",
        "Shevchenko","Pionerskaya","Turbinnaya","Elmash","Taganskaya"},
    {"Akademicheskaya","Yugo_zapadnaya","Volgogradskaya","Posadskaya","Geologicheskaya","Teatralnaya",
        "Gagarinskaya","Komsomolskaya","Shefskaya","Ozyornaya","Italyanskaya","Kalinovskaya"},
    {"Sovhoznaya","Voennaya","Aviatsionnaya","Dvorets_sporta","Geologicheskaya",
        "Kuybyshevskaya","Vostochnaya","Gagarinskaya","Vilonovskaya"},
    {"Keramicheskaya","Vtorchermet","Samolyotnaya","Botanicheskaya","Parkovaya","Mayakovskaya",
        "Oborony_square","Kuybyshevskaya","Teatralnaya","Shevchenko","Uralskaya","Zvezda",
        "I_Pyatiletki_square","Pobedy"},
    {"Himmash","Nizhne_Isetskaya","Uktusskie_Gory","Shcherbakovskaya","Botanicheskaya","Chkalovskaya",
        "Bazhovskaya","Geologicheskaya","1905_year_square","Dinamo","Uralskaya","Mashinostroiteley",
        "Uralmash","Prospekt_Kosmonavtov","Bakinskih_Komissarov"},
    {"Moskovskaya","Kommunarov_square","City","Uralskaya","Pionerskaya","Gagarinskaya","Vtuzgorodok",
        "Sibirskaya","Oborony_square","Bazhovskaya","Dvorets_sporta","Posadskaya","Moskovskaya"}
};
map<string,int> index;
int dist[71][71];
int main()
{
    int i,j,k,n,tot,x,y;
    string s,t;
    for (tot=i=0;i<8;++i)
        for (j=0;j<station[i];++j)
            if (index.find(line[i][j]) == index.end())
                index[line[i][j]]=++tot;
    memset(dist,44,sizeof(dist));
    for (i=0;i<8;++i)
    {
        x=index[line[i][0]];
        for (j=1;j<station[i];++j,x=y)
        {
            y=index[line[i][j]];
            dist[x][y]=dist[y][x]=1;
        }
    }
    for (i=1;i<=tot;++i)  dist[i][i]=0;
    for (k=1;k<=tot;++k)
        for (i=1;i<=tot;++i)
            for (j=1;j<=tot;++j)
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
    for (cin >> n;n;--n)
    {
        cin >> s >> t;
        x=index[s],y=index[t];
        cout << dist[x][y] << endl;
    }
    return 0;
}
//by zzy