11338 - Minefield

[andmej]

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!

[rio]

Dijkstra's algorithm using C++ STL's priority_queue runs fast enough.
I think your code has a problem when getting adjacent nodes.
Don't iterate through all nodes every time to get adjacent nodes.

-----
Rio

[andmej]

Thanks Rio for you answer.

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.


You can also download the full code from (link removed).

Thanks a lot for your help!

[rio]

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

[andmej]

Thanks Rio for your answer.

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!

[rio]

You could use an algorithm similar to Closest Pair Problem.

-----
Rio

[andmej]

Thanks Rio for your answer.

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!

[rio]

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

[andmej]

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.

[f74956227]

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 10010
using 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;   
}


[roticv]

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.