## 11338 - Minefield

Moderator: Board moderators

### 11338 - Minefield

Hello.

I am using Dijkstra's algorithm to find the length of the shortest path from safe-point (0, 0) to safe-point (w, h). If this length is less than the given constraint I print "I am lucky!", else I print "Boom!".

However, I am getting Time Limit Exceeded. Is there a faster algorithm?

I implemented Dijkstra's algorithm using C++ STL's priority_queue.

Thanks in advance for the help!
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

andmej
Experienced poster

Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Dijkstra's algorithm using C++ STL's priority_queue runs fast enough.
Don't iterate through all nodes every time to get adjacent nodes.

-----
Rio

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

I am not iterating over all nodes to get the adjacent nodes. I have a STL map of vectors of nodes, which gives me the adjacent nodes of a certain node. I'm not sure if a map is fast enough to retrieve the neighbors of each node. I'll try to improve the speed a little and if I can't get it Accepted, I'll post my code so you can check it out.

Thanks again!

Edit: I'm going a little desperate, so here's my source code so you can check it out. It's heavily commented for your understanding.

Code: Select all
`I got accepted.`

Thanks a lot for your help!
Last edited by andmej on Thu Mar 06, 2008 6:34 pm, edited 2 times in total.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

andmej
Experienced poster

Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

insert() in graph class is causing TLE.
It takes O(n^2logn) time, and its too slow for n ~ 10000.
You must find more faster way.

-----
Rio

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Can you give me any advice in how could I improve the running time it takes to insert a new node?

Perhaps map is not the appropriate data structure for this graph representation. I'd love to hear any ideas.

Thanks!
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

andmej
Experienced poster

Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

You could use an algorithm similar to Closest Pair Problem.

-----
Rio

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Do you mean using the closet pair algorithm to determine which points are at most 1.5 away from the point I want to insert?

I read about the function lower_bound of the STL maps. It finds the first element which compares greater than a given parameter. Since the map in my implementation is sorted by lexicographical order, I thought in finding the points which are lexicographically greater than the insertion point minus 1.5 in each x and y axis.

What do you think of this approach? Do you think it could work fast enough?

Thanks! And excuse me if I'm being a problem for you!
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

andmej
Experienced poster

Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Well, I don't know if STL map is proper for edge representation or not.
I used
Code: Select all
`typedef pair<int,double> Edge;vector<Edge> *edge=new vector<Edge>[n]`

for edge representation.

Anyway, simple O(n^2) algorithm to detect the edges could also get AC, though its rather slow.
-----
Rio

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Thanks, Rio!

Finally I got it accepted. I think the test cases are not too strong, though, since my program takes about 2 seconds with a 1000 point test case.

I used simple O(n^2) algorithm to detect neighbor vertexes of a given point, as Rio suggested. I exploited the fact that C++ STL's map keeps element sorted.
Last edited by andmej on Thu Mar 06, 2008 6:32 pm, edited 1 time in total.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

andmej
Experienced poster

Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### Re: 11338 - Minefield

Could someone please help with the code getting TLE ... ? I use the STL priority queue but still too slow...

Code: Select all
`#include <iostream>#include <map>#include <cmath>#include <vector>#include <queue>#define MAX 10010using namespace std;typedef struct node_info{   double x,y;}NODE;typedef pair<int, int> NodePair;map<NodePair, double> Weight;vector<int>adj[MAX];NODE node[MAX];int Vnum,W,H;double D,distances[MAX],MAXD = 1e9;bool visited[MAX];double find_dis(int i, int j){   return sqrt((node[i].x-node[j].x)*(node[i].x-node[j].x) + (node[i].y-node[j].y)*(node[i].y-node[j].y));   }void dijkstra(int start){     priority_queue< pair<double, int> > queue;     pair<double, int> nodotmp;     NodePair edge;     int i, j, now, next;       for(i=0; i<MAX; i++)   {       distances[i] = MAXD;       visited[i] = false;    }     distances[start] = 0.0;    queue.push(pair<double, int> (distances[start], start));     while(!queue.empty())   {       nodotmp = queue.top();         queue.pop();       now = nodotmp.second;       if (!visited[now])      {            visited[now] = true;            for (j = 0; j<adj[now].size(); j++)            {            next = adj[now][j];            edge = make_pair(now, next);              if (!visited[next] && Weight[edge] > 0.0 && distances[now] + Weight[edge] < distances[next])            {                   distances[next] = distances[now] + Weight[edge];                   queue.push(pair <double,int>(-distances[next], next));            }         }      }            }}int main(){   //freopen("test.in","r",stdin);   char in[10];   int i,j;   double tmpdis;   NodePair tmppair;      while(scanf("%s",in)==1)   {      if(in[0]=='*')break;      W = atoi(in);      scanf("%d",&H);            //initialization the data      Weight.clear();      for(i=0;i<MAX;i++) adj[i].clear();            //read the node and read the position      scanf("%d",&Vnum);      node[1].x = node[1].y = 0.0;   //first node      for(i=2;i<=Vnum+1;i++)         scanf("%lf %lf",&node[i].x,&node[i].y);      Vnum += 2;                  //last node      node[Vnum].x = (double)W, node[Vnum].y = (double)H;            //read the distance constraint      scanf("%lf",&D);         //start to find the weight      for(i=1;i<=Vnum;i++)         for(j=1;j<=Vnum;j++)         {            tmppair = make_pair(i,j);            tmpdis = find_dis(i,j);            if(tmpdis <= 1.5)            {               adj[i].push_back(j);               Weight[tmppair] = tmpdis;            }            else               Weight[tmppair] = -1;         }            //start to dijkstra find the shortest path.      dijkstra(1);      if(distances[Vnum]<=D)         printf("I am lucky!\n");      else         printf("Boom!\n");         }   return 0;   }`
electron
f74956227
New poster

Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan

### Re: 11338 - Minefield

Inserting into a map takes O(lg n) and hence you got TLE.

Using O(n^2) algorithm to generate all the edges result in my code taking 0.7+s. I think using kd-tree will result in faster runtime.
roticv
Learning poster

Posts: 63
Joined: Sat Dec 11, 2004 9:28 am