Dijkstra should pass, I just make a submission using JAVA, and it took less than a second to complete each task.
As I have mentioned, each value in the matrix can go up to 10^9, your solution can encounter a number overflow problem, which can effect the running time.
My code:
<!-- language:java -->
static int[]X = {0,1,0,-1};
static int[]Y = {1,0,-1,0};
public static void main(String[] args) throws FileNotFoundException {
// PrintWriter out = new PrintWriter(new FileOutputStream(new File(
// "output.txt")));
PrintWriter out = new PrintWriter(System.out);
Scanner in = new Scanner();
int n = in.nextInt();
long[][]map = new long[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
map[i][j] = in.nextLong();
}
}
PriorityQueue<Pos> q= new PriorityQueue();
long[][]dist = new long[n][n];
for(long[]a : dist){
Arrays.fill(a,Long.MAX_VALUE);
}
q.add(new Pos(0,0,map[0][0]));
dist[0][0] = map[0][0];
while(!q.isEmpty()){
Pos p = q.poll();
if(dist[p.x][p.y] == p.cost){
for(int i = 0; i < 4; i++){
int x = p.x + X[i];
int y = p.y + Y[i];
if(x >= 0 && y >= 0 && x < n && y < n && dist[x][y] > dist[p.x][p.y] + map[x][y] ){
dist[x][y] = dist[p.x][p.y] + map[x][y];
q.add(new Pos(x,y,dist[x][y]));
}
}
}
}
out.println(dist[n - 1][n - 1]);
out.close();
}
static class Pos implements Comparable<Pos>{
int x, y;
long cost;
public Pos(int x, int y, long cost) {
super();
this.x = x;
this.y = y;
this.cost = cost;
}
@Override
public int compareTo(Pos o) {
// TODO Auto-generated method stub
return Long.compare(cost, o.cost );
}
}
Update:
I think your Dijkstra implementation is not correct:
for frontier.Len() > 0 {
element := heap.Pop(&frontier).(*Item)
vertex, cost := element.value, element.priority
//You didn't check for visited vertex here!
visited[vertex] = true
neighbors := graph[vertex]
for vertex_new, cost_new := range(neighbors){
if !visited[vertex_new]{//You can add same vertex multiple times here!
if vertex_new == end{
return cost + cost_new
}
heap.Push(&frontier, &Item{
value: vertex_new,
priority: cost + cost_new,
})
}
}
}
In your implementation, you only update visited when the vertex pop out of the heap, thus, one vertex can be added and processed multiple time, so, it will significantly increase your time complexity.
To fix
for frontier.Len() > 0 {
element := heap.Pop(&frontier).(*Item)
vertex, cost := element.value, element.priority
if !visited[vertex]{
visited[vertex] = true
neighbors := graph[vertex]
for vertex_new, cost_new := range(neighbors){
if !visited[vertex_new]{
if vertex_new == end{
return cost + cost_new
}
heap.Push(&frontier, &Item{
value: vertex_new,
priority: cost + cost_new,
})
}
}
}