I have been trying to solve problem 3652 (Lazy Jumping Frog) from the Live Archive, but I keep on getting Time Limit Exceeded.
I am using Dijkstra's algorithm to solve it. My code is written in C++, and I'm using the "set" data structure from the STL to get the node with the shortest distance to the source node in each iteration, as well as to do the edge relaxation step efficiently.
This is my code:
EDIT: code removed.
Lazy Jumping Frog - 3652 (Live Archive)
Moderator: Board moderators
Lazy Jumping Frog - 3652 (Live Archive)
Last edited by zxul767 on Mon Nov 26, 2007 3:10 am, edited 1 time in total.
Still can't get this problem Accepted...
... Today I found a good idea to implement Dijkstra's algorithm when you know that the edge weights in the graph are in a certain range, say [0,k), using k simple queues. This improves the relaxation step from O(log (n)) to O(1).
However, I am still getting TLE. Here is my new code:
EDIT: code removed.
Thanks for your help!
However, I am still getting TLE. Here is my new code:
EDIT: code removed.
Thanks for your help!
Last edited by zxul767 on Mon Nov 26, 2007 3:10 am, edited 1 time in total.
Problem finally solved!
After observing that I was pushing a node more than once in my queue ring, and that my program was wasting time trying to update neighbor nodes from such repeated nodes, I reduced the execution time and finally got Accepted.
Well, no one replied to this post, but it might be helpful to someone else in the future![:D](./images/smilies/icon_biggrin.gif)
Well, no one replied to this post, but it might be helpful to someone else in the future
![:D](./images/smilies/icon_biggrin.gif)
I am getting TLE in 929
I am getting TLE in 929. I used dijkstra for it. I check that every node once popped from the queue is not inserted again. Moreover I also break the loop when destination is popped. any other optimization needed ? Is it possible to solve this problem with Dijkstra only. I saw in the board some other way with 9 queues to solve it.
Here is my code ..
I would be greatful if someone can propose some optimization to solve the problem. Thank you
Here is my code ..
Code: Select all
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int dr[]={-1,0,1,0};
int dc[]={0,1,0,-1};
#define INF 1000000000
const int MAXN = 1000 * 1000 + 1 ;
int R , C ;
int w[1002*1002];
bool out[1002*1002];
int dist[MAXN];
int heap[MAXN + 1];
int scratch[MAXN + 1];
int heap_size;
void update_heap(int u)
{
int q = scratch[u],p;
while(q > 1)
{
p = q / 2;
if(dist[heap[q]] < dist[heap[p]])
{
swap(scratch[heap[p]],scratch[heap[q]]);
swap(heap[p],heap[q]);
q = p;
}
else
break;
}
}
void heapify(int i)
{
int q = i,m;
while(true)
{
m = q;
if(2 * q <= heap_size && dist[heap[2 * q]] < dist[heap[m]])
m = 2 * q;
if(2 * q + 1 <= heap_size && dist[heap[2 * q + 1]] < dist[heap[m]])
m = 2 * q + 1;
if(m != q)
{
swap(scratch[heap[q]],scratch[heap[m]]);
swap(heap[q],heap[m]);
q = m;
}
else
break;
}
}
int src , dest ;
int main(){
int kase , i , u,v,c , r , cost , nr , nc ;
scanf("%d",&kase);
while(kase--)
{
scanf("%d %d",&R,&C);
for(i=0;i<R*C;++i){
scanf("%d",&w[i]);
out[i] = false ;
dist[i] = INF;
scratch[i] = i + 1;
heap[i + 1] = i;
}
heap_size = R * C ;
src = 0 ; dest = R * C - 1 ;
dist[src] = w[0];
update_heap(src);
while(heap_size > 1)
{
u = heap[1];
if(u==dest)break ;
scratch[heap[heap_size]] = 1;
heap[1] = heap[heap_size];
heap_size--;
heapify(1);
out[u] = true ;
c = u % C ; r = u / C ;
for(i=0;i<4;++i){
nr = r + dr[i] ;
nc = c + dc[i] ;
if((nr<0||nr>=R) || (nc<0||nc>=C))continue ;
v = nr * C + nc ;
if(out[v])continue ;
cost = dist[u] + w[v] ;
if( cost < dist[v] ){
dist[v] =cost ;
update_heap(v) ;
}
}
}
printf("%d\n",dist[dest]);
}
return 0 ;
}
In good company
How are you mens? help-me!! Help-me!!
I have a code source for the solution of this problem, but the code is presenting mistake, anybody can repair for me please because do not get, after harmonizing sends to my e-mail.
help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!!
Thanks.
Erasmo Carvalho - erasmosud@yahoo.com.br
Implemented in Java;
![:o](./images/smilies/icon_eek.gif)
![:o](./images/smilies/icon_eek.gif)
![:o](./images/smilies/icon_eek.gif)
help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!!
Thanks.
Erasmo Carvalho - erasmosud@yahoo.com.br
Implemented in Java;
Code: Select all
public static final int agua = -1;
public static final int libre = 1;
public static final int fueraPantano = -2;
public static final int enteroMaximo = 999999;
public static final int energia[][] = { { 7, 6, 5, 6, 7 },{ 6, 3, 2, 3, 6 },
{ 5, 2, 0, 2, 5 },{ 6, 3, 2, 3, 6 },
{ 7, 6, 5, 6, 7 } };
PriorityQueue<Nodo> cp = new PriorityQueue<Nodo>();
public static void main(String[] args) {
int c = 0, r = 0, cs = 0, rs = 0, ct = 0, rt = 0, b;
int c1, r1, c2, r2;
int i, j, k;
int[][] pantano = null;
int[][] costo = null;
Scanner in = new Scanner(System.in);
// leer las dimensiones del pantano
c = in.nextInt();
r = in.nextInt();
while (c > 0) {
// crear el pantano y matriz de costos
pantano = new int[r + 4][c + 4];
costo = new int[r + 4][c + 4];
// indicar que la fila 0 y columa 0
// estan fuera del pantano
for (i = 0; i < c + 4; i++)
pantano[0][i] = pantano[1][i] = fueraPantano;
for (i = 0; i < r + 4; i++)
pantano[i][0] = pantano[i][1] = fueraPantano;
for (i = 2; i < c + 4; i++)
pantano[r + 2][i] = pantano[r + 3][i] = fueraPantano;
for (i = 2; i < r + 4; i++)
pantano[i][c + 2] = pantano[i][c + 3] = fueraPantano;
// Marcar las celdas del pantano como libres
// y los costos como un entero grande
for (i = 2; i < r + 2; i++) {
for (j = 2; j < c + 2; j++) {
pantano[i][j] = libre;
costo[i][j] = enteroMaximo;
}
}
// leer el origen y el destino
cs = in.nextInt();
rs = in.nextInt();
ct = in.nextInt();
rt = in.nextInt();
// leer el numero de zonas acuosas
b = in.nextInt();
for (i = 0; i < b; i++) {
// leer las cordenadas de la region
c1 = in.nextInt();
r1 = in.nextInt();
c2 = in.nextInt();
r2 = in.nextInt();
c1 += 1;
c2 += 1;
r1 += 1;
r2 += 1;
for (k = r1; k <= r2; k++) {
for (j = c1; j <= c2; j++) {
pantano[k][j] = agua;
}
}
}
cs++;
rs++;
ct++;
rt++;
// ver(pantano,r, c);
// ver(costo,r, c);
dijkstra(pantano, costo, rs, cs, rt, ct);
if (costo[rt][ct] < enteroMaximo)
System.out.println(costo[rt][ct]);
else
System.out.println("Impossible");
c = in.nextInt();
r = in.nextInt();
}
}
public static void dijkstra(int[][] pantano, int[][] costo,int rs, int cs,int rt, int ct) {
int rv, cv; int i, j;
Nodo filcol;
PriorityQueue<Nodo> cp = new PriorityQueue<Nodo>();
costo[rs][cs] = 0;
rv = rs;
cv = cs;
cp.add(new Nodo(0, rs, cs));
while (!cp.isEmpty()) {
filcol = cp.remove();
rv = filcol.fila;
cv = filcol.col;
for (i = -2; i < 3; i++) {
for (j = -2; j < 3; j++) {
if (pantano[rv + i][cv + j] == libre) {
if (costo[rv + i][cv + j] > (costo[rv][cv] + energia[i + 2][j + 2])) {
costo[rv + i][cv + j] = costo[rv][cv] + energia[i + 2][j + 2];
cp.add(new Nodo(costo[rv + i][cv + j],rv + i, cv + j));
}
}
}
}
}
}
class Nodo implements Comparable<Nodo> {
int costo, fila, col;
public Nodo(int costo, int fila, int col) {
this.costo = costo;
this.fila = fila;
this.col = col;
}
public int compareTo(Nodo other) {
return costo - other.costo;
}
}
Erasmo Carvalho
-
- New poster
- Posts: 9
- Joined: Sat Dec 01, 2007 1:42 am
Thank you.
Thank you very much Santos.
You are the Maximum!!!
See you later
I hope to help-you one day.
Erasmo[/b]
You are the Maximum!!!
See you later
I hope to help-you one day.
Erasmo[/b]
Erasmo Carvalho