IPST59: Wormholes

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

const int N = 30;

typedef pair<int, int> pii;

map<pii, int> coorToIdx;
pii coor[N + N];
vector<int> adj[N + N];
int dist[N + N][N + N];

int nVertex = 0;
int addCoor(int x, int y){
    map<pii, int>::iterator itr = coorToIdx.find(pii(x, y));
    if(itr == coorToIdx.end()){
        coorToIdx.emplace(pii(x, y), nVertex);
        coor[nVertex] = pii(x, y);
        return nVertex++;
    }
    return itr -> second;
}

int distance(pii &u, pii &v){
    return abs(u.first - v.first) + abs(u.second - v.second);
}

int main(){

    int nPortal, Q;
    scanf("%d%d", &nPortal, &Q);
    for(int i = 1; i <= nPortal; ++i){
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        int u = addCoor(x1, y1);
        int v = addCoor(x2, y2);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int u = 0; u < nVertex; ++u){
        for(int v = 0; v < nVertex; ++v){
            dist[u][v] = distance(coor[u], coor[v]);
        }
    }
    for(int u = 0; u < nVertex; ++u){
        for(int v : adj[u]){
            dist[u][v] = 0;
        }
    }

    // Floyd-Warshall Algorithm
    for(int k = 0; k < nVertex; ++k){
        for(int u = 0; u < nVertex; ++u){
            for(int v = 0; v < nVertex; ++v){
                dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v]);
            }
        }
    }

    // Query
    for(int q = 1; q <= Q; ++q){
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        pii st = pii(x1, y1);
        pii ed = pii(x2, y2);
        int ans = distance(st, ed);
        for(int u = 0; u < nVertex; ++u){
            for(int v = 0; v < nVertex; ++v){
                if(u == v){
                    continue;
                }
                ans = min(ans, distance(st, coor[u]) + dist[u][v] + distance(coor[v], ed));
            }
        }
        cout << ans << '\n';
    }

    return 0;
}