Timus: 1119 - Metro

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>

using namespace std;

struct Grafo
{
    vector <vector <int> > Adj;
    vector <vector <bool> > diag;

    void bfs(int x, int y)
    {
        queue<pair<int, int> > cola;
        cola.push(make_pair(x, y));
        Adj[x][y] = 0;

        while(cola.size())
        {
            x = cola.front().first, y = cola.front().second;
            cola.pop();

            if(x+1 < Adj.size() && Adj[x][y]+10000 < Adj[x+1][y])
            {
                cola.push(make_pair(x+1, y));
                Adj[x+1][y] = Adj[x][y]+10000;
            }
            if(y+1 < Adj[0].size() && Adj[x][y]+10000 < Adj[x][y+1])
            {
                cola.push(make_pair(x, y+1));
                Adj[x][y+1] = Adj[x][y]+10000;
            }
            if(x+1 < Adj.size() && y+1 < Adj[0].size())
            {
                if(diag[x+1][y+1] && Adj[x][y]+14142 < Adj[x+1][y+1])
                {
                    cola.push(make_pair(x+1, y+1));
                    Adj[x+1][y+1] = Adj[x][y]+14142;
                }
            }
        }
    }

    void leer()
    {
        int n, m, d, a, b;
        cin >> n >> m >> d;
        Adj = vector <vector <int> > (m+1, vector <int> (n+1, 999999999));
        diag = vector <vector <bool> > (m+1, vector <bool> (n+1, false));

        for(int i=0; i<d; i++)
        {
            cin >> a >> b;
            diag[b][a] = true;
        }
        bfs(0, 0);

        int v = (int)round(Adj[m][n]/100.0);
        cout << v << endl;
    }

};

int main()
{
    Grafo g;
    g.leer();
    return 0;
}