TLE using DP for Timus Online Judge

Question

I was solving problem timusOJ Metro. I solved it using DP but I am getting TLE. I don't know how to do it better? Solution in Ideone. Help!

#include <bits/stdc++.h>

using namespace std;

double dis[1005][1005];

map< pair< int, int >, int > m;

int N, M, K;

double min( double a, double b ){

    if( a < b )
        return a;

    return b;
}

int main(){

    cin >> M >> N;

    cin >> K;

    dis[0][0]= 0;

    for( int i= 1; i<= N; ++i )
        dis[i][0]= 100*i;

    for( int j= 1; j<= M; ++j )
        dis[0][j]= 100*j;

    for( int i= 0, x,y; i< K; ++i ){

        scanf( "%d%d", &x, &y );
        m[{y,x}]++; 
    }

    double shortcut= sqrt(20000);

    for( int i= 1; i<= N; ++i )
        for( int j= 1; j<= M; ++j ){

            //cout << i << " " << j << "\n\t";

            if( m[{i,j}] > 0 ){

                dis[i][j]= min( dis[i-1][j-1] + shortcut , min(   
                                    dis[i-1][j] , dis[i][j-1] ) + 100 ) ;

                m[{i,j}]--;

            }else{

                dis[i][j]= min( dis[i-1][j], dis[i][j-1] ) + 100;

            }

        }

    cout << ceil(dis[N][M]) << endl;

}

P.S. I have problem in formatting code in this platform therefore ideone is used.

UPD: Accepted :)

Answer 1

Read the question wrong , I claim that by triangular inequality The distance to go to a block diagonally is lesser than travelling right and up.! I will submit and explain soon..