10986 - Sending email

[prashantharshi]

here naive dijksra will get TLE
so use dijkstra with heap
u can also use STL priority queue
here is my AC code
http://ideone.com/fEGjgN

[brianfry713]

Input:

Code: Select all

1
2 1 0 1
0 1 10000

AC output:

Code: Select all

Case #1: 10000

[groovy.kmilo]

Hello

I am trying to solve this problem and got TLE with Dijsktra and FloydWarshall, now i implemented Dijsktra with heap but i am still getting TLE

Any idea what is wrong or what i can change to improve mi code

thanks in advance

Code in java:

Code: Select all

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;



public class sendingEmail {



	static int m[][];
	static final int INF = Integer.MAX_VALUE / 2;

	public static void main(String[] args) throws Exception {

		BufferedReader in = new BufferedReader( new InputStreamReader( System.in ) );
		BufferedWriter out = new BufferedWriter( new OutputStreamWriter(System.out));

		int casos = Integer.parseInt(in.readLine());
		int num_caso = 1;

		while (casos>0) {

			StringTokenizer stk = new StringTokenizer(in.readLine());
			int cantidad_nodos = Integer.parseInt(stk.nextToken());
			int aristas = Integer.parseInt(stk.nextToken());
			int inicio = Integer.parseInt(stk.nextToken());
			int destino = Integer.parseInt(stk.nextToken());

			inicializarMatriz(cantidad_nodos);

			for (int i = 0; i < aristas; i++) {
				stk = new StringTokenizer(in.readLine());
				int a = Integer.parseInt(stk.nextToken());
				int b = Integer.parseInt(stk.nextToken());
				int peso = Integer.parseInt(stk.nextToken());
				m[a][b] = peso;
				m[b][a] = peso;
			}


			out.write("Case #"+num_caso+": ");

			List<Nodo>[] nodos = new List[cantidad_nodos];
			for (int i = 0; i < cantidad_nodos; i++) {
				nodos[i] = new ArrayList<>();
				for (int j = 0; j < cantidad_nodos; j++) {
					if (m[i][j] != INF) {
						nodos[i].add(new Nodo(j, m[i][j]));
					}
				}
			}
			int[] dist = new int[cantidad_nodos];
			int[] pred = new int[cantidad_nodos];

			shortestPaths(nodos, inicio, dist, pred);

			int distancia= dist[destino];
			
//			int[][] pred = floydWarshall();
//			int distancia = m[inicio][destino];
			out.write(distancia==INF? "unreachable\n": distancia+"\n");

			casos--;
			num_caso++;
		}



		out.flush();
		out.close();
		in.close();

	}


	static void inicializarMatriz(int nodos) {
		m = new int[nodos][nodos];
		for (int i = 0; i < m.length; i++) {
			for (int j = 0; j < m[0].length; j++) {
				m[i][j]= INF;
			}
		}	
	}
	
	/**
	 * Dijkstra Heap
	 */
		 static void shortestPaths(List<Nodo>[] nodos, int s, int[] prio, int[] pred) {
			    Arrays.fill(pred, -1);
			    Arrays.fill(prio, INF);
			    prio[s] = 0;
			    PriorityQueue<Long> q = new PriorityQueue<>();
			    q.add((long) s);
			    while (!q.isEmpty()) {
			      long cur = q.remove();
			      int curu = (int) cur;
			      if (cur >>> 32 != prio[curu])
			        continue;
			      for (Nodo e : nodos[curu]) {
			        int v = e.t;
			        int nprio = prio[curu] + e.cost;
			        if (prio[v] > nprio) {
			          prio[v] = nprio;
			          pred[v] = curu;
			          q.add(((long) nprio << 32) + v);
			        }
			      }
			    }
			  }
	
			  static class Nodo {
			    int t, cost;
	
			    public Nodo(int t, int cost) {
			      this.t = t;
			      this.cost = cost;
			    }
			  }

}

[brianfry713]

Use class Main

[richatibrewal]

The following code is getting a WA. Plz help

Code: Select all

#include<cstdio>
#include<vector>
#include<climits>
#include<queue>
#define MAXLEN 20010
struct node
{
    int data,weight;
};

class compare
{
public:
    bool operator()(const node& a,const node& b)
    {
        return a.weight>b.weight;
    }
};
using namespace std;


priority_queue<node,vector<node>,compare> pq;
vector<node> graph[MAXLEN];
bool visited[MAXLEN];
int dist[MAXLEN],v,e,s,t;

void shortest_path()
{
    int i,j,m,n,p;

    dist[s]=0;
    node a={s,0};
    pq.push(a);

    while(!pq.empty())
    {
        node v1=pq.top();
        pq.pop();
      if((v1.data)==t)
            return;

        visited[v1.data]=true;
        i=v1.data;
        n=v1.weight;

//        printf("%d\n",i);

        for(j=0;j<graph[i].size();j++)
        {
            m=graph[i][j].data;
            p=graph[i][j].weight;
            if(dist[i]+p<dist[m] && !visited[m])
            {
                dist[m]=dist[i]+p;
                //if(!visited[m])
                {
                    node b={m,dist[m]};
                    pq.push(b);
                }
            }
        }
    }
}

int main()
{
    int i,j,cases,n,x,y,w;
    scanf("%d",&n);

    for(cases=1;cases<=n;cases++)
    {
        scanf("%d%d%d%d",&v,&e,&s,&t);

        for(i=0;i<v;i++)
        {
            dist[i]=INT_MAX;
            visited[i]=false;
        }

        for(i=0;i<e;i++)
        {
            scanf("%d%d%d",&x,&y,&w);
            node r={y,w};
            graph[x].push_back(r);
            node q={x,w};
            graph[y].push_back(q);
        }

        shortest_path();

        printf("Case #%d: ",cases);
        if(dist[t]==INT_MAX)
            printf("unreachable\n");
        else
            printf("%d\n",dist[t]);

        for(i=0;i<v;i++)
            graph[i].clear();
    }
    return 0;

}

But if I am removing the following lines, the code is getting accepted.

Code: Select all

 if((v1.data)==t)
            return;

Why is it so? If v1.data is equal to t, visited[t] becomes true. Then it won't be able to modify the distance. So why is this wrong?

[diegoteran]

I don't know why but I keep getting TLE. Is there some way to make it faster? :/

Code: Select all

#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> pii;

#define mp make_pair
#define fst first 
#define snd second 
#define MAXN 20005
#define MAXM 50005

int T, N, M, s, t, x, y, w, i, j;

struct edge{
	int node, next, cost;
};

int start[MAXN], nextEdge;
bool v[MAXN];
edge graph[MAXM];

void addEdge(int a, int b, int c){
	graph[nextEdge].cost = c;
	graph[nextEdge].node = b;
	graph[nextEdge].next = start[a];
	start[a] = nextEdge++;
}

priority_queue<pii, vector<pii>, greater<pii> > q;
void init(){
	nextEdge = 1;
	fill(start, start+MAXN, 0);
	fill(v, v+MAXN, false);
}

int dijkstra(int u){

	while(!q.empty()) q.pop();

	q.push(mp(0, u));
	
	while(!q.empty()){
		pii p = q.top(); q.pop();
		if (v[p.snd]) continue;
		v[p.snd] = true;

		if(p.snd == t)
			return p.fst;

		for(int k = start[p.snd]; k; k = graph[k].next){
			if(!v[graph[k].node])
				q.push(mp(p.fst + graph[k].cost, graph[k].node));
		}
	}

	return -1;
}


int main(){
	int tc = 0;
	scanf("%d", &T);
	while (tc++, T--){
		init();
		scanf("%d %d %d %d", &N, &M, &s, &t);
		for (i = 0; i < M; i++){
			scanf("%d %d %d", &x, &y, &w);
			addEdge(x, y, w);
			addEdge(y, x, w);
		}

		x = dijkstra(s);
		if(x == -1)
			printf("Case #%d: unreachable\n", tc);
		else
			printf("Case #%d: %d\n", tc, x);
	}


}