OJ Board

The Online Judge board
https://onlinejudge.org/board/

10986 - Sending email

https://onlinejudge.org/board/viewtopic.php?t=9918

Page 4 of 5

Re: 10986 - Sending email

Posted: Sat Mar 19, 2011 7:26 am
by avdtech
Just a little correction in the test cases posted by neilor -

TC#66 is wrong -

it should be
3 1 0 2
0 2 103

instead of
2 1 0 2
0 2 103

since the nodes are number from 0 to n-1.

Thanks for the cases. It helped a lot.

Re: 10986 - Sending email

Posted: Sat Mar 26, 2011 6:59 pm
by DD
neilor wrote:Hello People.

Follow some test cases to the problem (test using uva tookit: http://uvatoolkit.com/problemssolve.php)

Code: Select all

75

6 3 0 2
0 1 50
2 1 70
0 2 150

2 1 0 1
1 0 33333

2 0 0 0

2 1 0 1
1 0 111

2 2 0 1
1 0 100
0 1 33

2 1 0 1
0 1 100
3 3 2 0
0 1 100
0 2 200
1 2 50
2 0 0 1



14 20 13 2
0 1 123
1 2 467
2 3 478
4 5 578
5 3 47
2 6 256
7 2 246
5 9 245
5 3 1245
8 2 575
9 4 235
2 8 437
9 12 367
13 7 587
11 9 476
9 5 34
11 13 35
13 10 2
12 11 7
12 6 235

14 16 11 2
0 1 123
1 2 467
2 3 478
4 5 578
5 3 47
2 6 256
7 2 246
5 9 245
5 3 1245
9 4 235
9 12 367
13 7 587
11 9 476
9 5 34
13 11 2
12 11 7

4 5 0 3
0 2 17
0 3 18
2 3 11
2 1 2
0 1 4

4 7 0 3
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

4 7 2 1
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 0 4
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

14 20 13 2
0 1 123
1 2 4567
2 3 4578
4 5 5678
5 3 47
2 6 256
7 2 2346
5 9 2345
5 3 12345
8 2 5785
9 4 2345
2 8 4367
9 12 3467
13 7 5687
11 9 4576
9 5 34
11 13 345
13 11 2
12 11 7
12 6 235898

14 20 13 2
0 1 123
1 2 467
2 3 478
4 5 578
5 3 47
2 6 256
7 2 246
5 9 245
5 3 1245
8 2 575
9 4 235
2 8 437
9 12 367
13 7 587
11 9 476
9 5 34
11 13 35
13 10 2
12 11 7
12 6 235

14 16 11 2
0 1 123
1 2 467
2 3 478
4 5 578
5 3 47
2 6 256
7 2 246
5 9 245
5 3 1245
9 4 235
9 12 367
13 7 587
11 9 476
9 5 34
13 11 2
12 11 7


6 7 0 4
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 3 0
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 0 2
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 0 1
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 0 0
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 1 2
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 2 3
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4


5 5 0 4
0 1 3
1 0 2
1 0 1
0 1 4
1 4 1000

6 9 5 2
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 3 2
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 4 3
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 5 5
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 13 0 5
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4
0 2 7
1 0 1
0 3 8
2 3 1
2 1 2
5 3 100

6 13 1 5
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4
0 2 7
1 0 1
0 3 8
2 3 1
2 1 2
5 3 100

6 13 2 5
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4
0 2 7
1 0 1
0 3 8
2 3 1
2 1 2
5 3 100

6 13 3 4
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4
0 2 7
1 0 1
0 3 8
2 3 1
2 1 2
5 3 100

6 13 2 5
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4
0 2 7
1 0 1
0 3 8
2 3 1
2 1 2
5 3 100

6 9 0 5
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 5 2
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 3 0
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

8 7 4 6
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

1 1 0 0
0 0 25

5 4 0 4
1 2 404
3 4 505
3 2 606
1 0 100

6 7 5 0
2 3 404
4 5 505
3 5 606
4 3 303
1 2 100
0 4 201
1 5 707

4 3 0 2
0 1 50
2 1 70
0 2 150

4 3 1 2
0 1 50
2 1 70
0 2 150

6 9 5 0
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 0 5
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 5 2
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 3 0
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

8 7 4 6
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 6 4
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 2 5
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 2 6
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 2 7
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 3 7
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 0 7
4 3 404
2 3 505
1 2 606
0 1 303
4 5 100
5 6 201
6 7 707

8 7 0 7
0 1 404
1 2 505
2 3 606
3 4 303
4 5 100
5 6 201
6 7 707

8 7 0 7
0 1 404
3 2 505
2 1 606
5 6 303
4 5 100
3 4 201
6 7 707

8 7 0 7
4 3 404
4 5 505
5 6 606
3 2 303
2 1 100
6 7 201
0 1 707

8 7 0 7
1 2 404
6 7 505
3 4 606
0 1 303
5 4 100
5 6 201
3 2 707

8 7 3 7
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 3 7
2 3 404
1 2 505
0 1 606
4 0 303
5 4 100
6 5 201
6 7 707

1 1 0 0
0 0 25

5 4 0 4
1 2 404
3 4 505
3 2 606
1 0 100

6 7 0 5
2 3 404
4 5 505
3 5 606
4 3 303
1 2 100
0 4 201
1 5 707

6 3 0 2
0 1 50
2 1 70
0 2 150


2 1 0 1
1 0 33333

2 1 0 2
0 2 103

2 0 0 1

2 0 1 2

4 3 0 3
2 0 50
1 2 70
3 1 150

2 1 0 1
0 1 100

3 3 2 0
0 1 100
0 2 200
1 2 50

4 3 0 3
2 0 50
1 2 70
3 1 150

2 1 0 1
0 1 100

3 3 2 0
0 1 102
0 2 202
1 2 52

4 3 1 0
1 2 104
2 3 204
0 3 54
Thank you for providing the test case :lol:

TLE Sending email 10986

Posted: Tue Jun 07, 2011 6:51 pm
by LeonardoB
Hi.

I got tle in this problem using Dijkstra algorithm and priority queu.

Code: Select all

include <cstdlib>
#include <string>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <map>
#include <list>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <limits>
#include <cctype>
#include <queue>

using namespace std;

class Graph {

private:
	struct Node;

	class compare {

	private:
		int * dist;

	public:
		compare (int * d) : dist(d) {}
		bool operator () (const Node* n1, const Node* n2) {

			return dist[n1->id] < dist[n2->id];
		}
	};

	struct Edge {

		Node * begin, * end;
		int value;
		friend bool operator < (const Edge & e1, const Edge & e2) {
			return e1.value < e2.value;
		}
	};

	struct Node {
		
	public:
		
		int id;
		vector<Edge> next;
		bool visited;
	};

	Node* nodes;
	int* dist;
	int N;

public:
	
	Graph (int k) {
		N = k;
		nodes = new Node[k + 1];
		dist = new int[k + 1];

		for (size_t i = 0; i < k + 1; ++i)
			nodes[i].visited = false;
	}

	~Graph() {

		delete [] dist;
		delete [] nodes;
	}

	void add_node (int from, int to, int value) {
		nodes[from].id = from;
		nodes[to].id = to;

		Edge e = { &nodes[from], &nodes[to], value };
		nodes[from].next.push_back (e);
	}

	int dijkstra (int from, int to) {

		memset (dist, 0x3F3F3F3F, sizeof (int) * (N + 1));

		const compare c1 (dist);
		priority_queue<Node*, deque<Node*>, compare> q (c1);

		dist[from] = 0; 
		
		q.push (&nodes[from]);
		

		while (!q.empty()) {
			Node* t = q.top();
			q.pop();

			for (vector<Edge>::iterator it = t->next.begin(); it != t->next.end(); ++it) {

				it->end->visited = true;
				dist[it->end->id] = min (dist[it->end->id], dist[t->id] + it->value);

				q.push (it->end);
			}
		}

		return nodes[to].visited ? dist[to] : -1;
	}

};

int main() {

	int K, N, M, S, T, A, B, V;

	scanf ("%d", &K);

	for (size_t k = 0; k < K; ++k) {

		scanf ("%d %d %d %d", &N, &M, &S, &T);

		Graph g (N);

		for (size_t m = 0; m < M; ++m) {
			scanf ("%d %d %d", &A, &B, &V);
			g.add_node (A, B, V);
		}

		int out = g.dijkstra (min (S, T), max (S, T));

		if (out == -1) printf ("Case #%d: unreachable\n", k + 1);
		else printf ("Case #%d: %d\n", k + 1, out);

	}

	return 0;
}

Re: 10986 - Sending email

Posted: Thu Jul 07, 2011 1:10 am
by JohnsonWang
Hi All,

I'm having a similar issue - my submission is returning a TLE, however, it seems to work on all my local test cases just fine. I'm using a simple Dijkstra's, without any real optimisations.

Here is the code:

Code: Select all

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;

const int INF = 9e8;

int get_min_dist( int starting_node, int ending_node, map < int, vector < pair <int, int> > > adj_list, int num_nodes )
{
	vector <int> distances( num_nodes, INF );
	distances[starting_node] = 0;

	priority_queue < pair <int, int> > pq;
	pq.push( make_pair( starting_node, 0 ) );

	while( !pq.empty() )
	{
		pair <int, int> cur = pq.top();
		pq.pop();
	
		vector < pair <int, int> >::iterator it = adj_list[cur.first].begin();
		while( it != adj_list[cur.first].end() )
		{
			if( distances[it->first] > distances[cur.first] + it->second )
			{
				distances[it->first] = distances[cur.first] + it->second;
				pq.push( make_pair( it->first, distances[it->first] ) );
			}
			it++;
		}
	}

	return distances[ending_node];
}

int main()
{
	int num_test_cases;
	cin >> num_test_cases;

	for( int test_case_no = 1; test_case_no <= num_test_cases; test_case_no++ )
	{
		int num_nodes, num_edges, starting_node, ending_node;
		cin >> num_nodes >> num_edges >> starting_node >> ending_node;

		map < int, vector < pair <int, int> > > adj_list;
		for( int edge_no = 0; edge_no < num_edges; edge_no++ )
		{
			int from, to, cost;
			cin >> from >> to >> cost;
			adj_list[from].push_back( make_pair( to, cost ) );
			adj_list[to].push_back( make_pair( from, cost ) );
		}
	
		cout << "Case #" << test_case_no << ": ";
		int dist = get_min_dist( starting_node, ending_node, adj_list, num_nodes );
		if( dist == INF ) cout << "unreachable" << endl;
		else cout << dist << endl;
	}

	return 0;
}

Re: 10986 - Sending email

Posted: Sun Sep 11, 2011 3:01 pm
by shanto_0321
if we scan a='0',then why we do not get the value of a=48-'0'=0.
what is the problem.

Code: Select all

#include<stdio.h>
#include<math.h>
#include<string.h>
int main()
{
char a[23];
int i,s=0,len;
while(scanf("%s",a)!=EOF)
{
printf("%lld",a);
if((a-48)==0)
             break;
            
      else
{
len=strlen(a);
i=0;
while(a[i]!='\0')
           {          
           s=s+(a[i]-48)*(pow(2,(len))-1);
           i++;
           len--;
           }
printf("%lld",s);
printf("\n");
s=0;
}
}
return 0;
}

Re: 10986 - Sending email

Posted: Sun Jul 29, 2012 7:29 pm
by pranon
Is there something I can do to make my code more efficient? Or does it fall in an infinite loop for some test case?
Any pointers as to how the code can be made more efficient?
Thanks in advance :'(

Code: Select all

Code Edited

Re: 10986 - Sending email

Posted: Tue Jul 31, 2012 12:11 am
by brianfry713
Doesn't match the sample I/O.

Re: 10986 - Sending email

Posted: Tue Jul 31, 2012 8:12 am
by pranon
Ok, I'm extremely sorry I posted without removing the...
Ok, here's the code. getting ``Time Limit Exceeded".

Code: Select all

#include <stdio.h>
#include <string.h>

void djikstra(int i);
void insert(int i);
int pop(void);
void update(int i);
void initialize(void);
int adj[20003][20003], weight[20003][20003], dis[20003], iindex[20003], heap[20003], n, des, end=1, apoc;
char seen[20003];


int main()
{
    int t, m, source, a, b, w;
    register int x;
    scanf("%d", &t);
    for(x=1; x<=t; x++)
    {
        scanf("%d %d %d %d", &n, &m, &source, &des);
        apoc=n;
        if(x>1)
            initialize();
        while(m--)
        {
            scanf("%d %d %d", &a, &b, &w);
            adj[a][0]++;
            adj[b][0]++;
            weight[a][adj[a][0]]=w;
            weight[b][adj[b][0]]=w;
            adj[a][adj[a][0]]=b;
            adj[b][adj[b][0]]=a;
        }
        djikstra(source);
        printf("Case %c%d: ", '#', x);
        seen[des]==2?printf("%d\n", dis[des]):printf("unreachable\n");
        /*for(i=0; i<n; i++)
            if(seen[i]!=0)
                printf("i= %d, dis = %d\n", i, dis[i]);*/
    }
    return 0;
}

void djikstra(int source)
{
    int i, small;
    seen[source]=1;
    dis[source]=0;
    insert(source);
    while(apoc)
    {
        small=pop();
        apoc--;
        seen[small]=2;
        if(small==des)
            break;
        for(i=1; i<=adj[small][0]; i++)
            if(seen[adj[small][i]]!=2)
            {
                if(seen[adj[small][i]]==0)
                {
                    dis[adj[small][i]]= dis[small]+weight[small][i];
                    insert(adj[small][i]);
                    seen[adj[small][i]]=1;
                }
                else if(dis[adj[small][i]]>dis[small]+weight[small][i])
                {
                    dis[adj[small][i]]= dis[small]+weight[small][i];
                    update(adj[small][i]);
                }
            }
    }
    return;
}

void insert(int i)
{
    int cur=end, par=end>>1, temp;
    heap[end]=i;
    end++;
    while(par>=1 && dis[heap[par]]>dis[heap[cur]])
    {
        temp=heap[par];
        heap[par]=heap[cur];
        heap[cur]=temp;
        iindex[heap[cur]]=cur;
        cur=par;
        par>>=1;
    }
    iindex[heap[cur]]=cur;
    /*for(i=1; i<end; i++)
        printf("%d\n", heap[i]);*/
    return;
}

int pop(void)
{
    int node, even, odd, cur, min, temp;
    end--;
    node=heap[1];
    heap[1]=heap[end];
    iindex[heap[1]]=1;
    cur=1;
    even=2, odd=3;
    while(odd<end && (dis[heap[cur]]>dis[heap[even]] || dis[heap[cur]]>dis[heap[odd]]))
    {
        min=dis[heap[odd]]>dis[heap[even]]?even:odd;
        temp=heap[min];
        heap[min]=heap[cur];
        heap[cur]=temp;
        iindex[heap[min]]=min;
        iindex[heap[cur]]=cur;
        cur= min;
        even=cur<<1;
        odd=even+1;
    }
    /*for(i=1; i<end; i++)
        printf("%d\n", heap[i]);*/
    return node;
}

void update(int node)
{
    int i, m, temp;
    i=iindex[node];
    m=i>>1;
    while(m>=1 && dis[heap[i]]<dis[heap[m]])
    {
        temp=heap[m];
        heap[m]=heap[i];
        heap[i]=temp;
        iindex[heap[i]]=i;
        i=m;
        m>>=1;
    }
    iindex[node]=i;
    /*for(i=1; i<end; i++)
        printf("%d\n", heap[i]);*/
    return;
}

void initialize(void)
{
    int i;
    for(i=0; i<n; i++)
        adj[i][0]=0;
    memset(seen, 0, n*sizeof(char));
    end=1;
    return;
}
Thanks in advance.

Re: 10986 - Sending email

Posted: Wed Aug 01, 2012 3:42 am
by brianfry713
I used a C++ STL priority_queue in Dijkstra's algorithm. Is your queue logarithmic?

Re: 10986 - Sending email

Posted: Wed Aug 01, 2012 8:26 am
by pranon
Yes, I think it takes lg(n) operations to insert, pop and update some node in the worst case. It's an array stored like a heap.
I don't know stl. :(
I edited my code after getting accepted in 929. But still ``Time Limit Exceeded".

Code: Select all

#include <stdio.h>
#include <string.h>

void djikstra(int i);
void insert(int i);
int pop(void);
void update(int i);
void initialize(void);
int adj[20003][20003], weight[20003][20003], dis[20003], iindex[20003], heap[20003], n, des, end=1, apoc;
char seen[20003];


int main()
{
    int t, m, source, a, b, w;
    register int x;
    scanf("%d", &t);
    for(x=1; x<=t; x++)
    {
        scanf("%d %d %d %d", &n, &m, &source, &des);
        apoc=n;
        if(x>1)
            initialize();
        while(m--)
        {
            scanf("%d %d %d", &a, &b, &w);
            adj[a][0]++;
            adj[b][0]++;
            weight[a][adj[a][0]]=w;
            weight[b][adj[b][0]]=w;
            adj[a][adj[a][0]]=b;
            adj[b][adj[b][0]]=a;
        }
        djikstra(source);
        printf("Case %c%d: ", '#', x);
        seen[des]==2?printf("%d\n", dis[des]):printf("unreachable\n");
    }
    return 0;
}

void djikstra(int source)
{
    int i, small;
    seen[source]=1;
    dis[source]=0;
    insert(source);
    while(apoc)
    {
        small=pop();
        apoc--;
        seen[small]=2;
        if(small==des)
            break;
        for(i=1; i<=adj[small][0]; i++)
            if(seen[adj[small][i]]!=2)
            {
                if(seen[adj[small][i]]==0)
                {
                    dis[adj[small][i]]= dis[small]+weight[small][i];
                    insert(adj[small][i]);
                    seen[adj[small][i]]=1;
                }
                else if(dis[adj[small][i]]>dis[small]+weight[small][i])
                {
                    dis[adj[small][i]]= dis[small]+weight[small][i];
                    update(adj[small][i]);
                }
            }
    }
    return;
}

void insert(int i)
{
    int cur=end, par=end>>1, temp;
    heap[end]=i;
    end++;
    while(par>=1 && dis[heap[par]]>dis[heap[cur]])
    {
        temp=heap[par];
        heap[par]=heap[cur];
        heap[cur]=temp;
        iindex[heap[cur]]=cur;
        cur=par;
        par>>=1;
    }
    iindex[heap[cur]]=cur;
    return;
}

int pop(void)
{
    int node, even, odd, cur, min, temp;
    end--;
    node=heap[1];
    heap[1]=heap[end];
    iindex[heap[1]]=1;
    cur=1;
    even=2, odd=3;
    while((odd<end || even<end) && (dis[heap[cur]]>dis[heap[even]] || dis[heap[cur]]>dis[heap[odd]]))
    {
        if(odd<end)
            min=dis[heap[odd]]>dis[heap[even]]?even:odd;
        else
            min=dis[heap[even]]<dis[heap[cur]]?even:cur;
        if(min!=cur)
        {
            temp=heap[min];
            heap[min]=heap[cur];
            heap[cur]=temp;
            iindex[heap[min]]=min;
            iindex[heap[cur]]=cur;
        }
        cur= min;
        even=cur<<1;
        odd=even+1;
    }
    return node;
}

void update(int node)
{
    int i, m, temp;
    i=iindex[node];
    m=i>>1;
    while(m>=1 && dis[heap[i]]<dis[heap[m]])
    {
        temp=heap[m];
        heap[m]=heap[i];
        heap[i]=temp;
        iindex[heap[i]]=i;
        i=m;
        m>>=1;
    }
    iindex[node]=i;
    return;
}

void initialize(void)
{
    int i;
    for(i=0; i<n; i++)
        adj[i][0]=0;
    memset(seen, 0, n*sizeof(char));
    end=1;
    return;
}

Re: 10986 - Sending email

Posted: Thu Aug 02, 2012 12:00 am
by brianfry713
I think your priority queue must be too slow, my code gets AC in 0.22 seconds. If you can't figure out the C++ STL version try using a different implementation. My code doesn't update the queue when a shorter distance to a node is found, it just pushes another item onto the queue.

Re: 10986 - Sending email

Posted: Mon Aug 06, 2012 12:27 am
by mahade hasan
cut after AC.....

Re: 10986 - Sending email

Posted: Sun Aug 04, 2013 10:08 am
by setu basak

Code: Select all

#include<bits/stdc++.h>
using namespace std;
vector<int>g[20005];
int cost[20005][20005];
int d[20005];
struct node
{
    int u,w;
    node(int a,int b)
    {
        u=a;w=b;
    }
    bool operator < (const node& p)const
    {
        return w>p.w;
    }
};
void reset()
{
    for(int i=0;i<20005;i++)
        g[i].clear();
}
int dijkstra(int n,int src,int des)
{
    memset(d,63,sizeof(d));
    priority_queue<node>q;
    q.push(node(src,0));
    d[src]=0;
    while(!q.empty())
    {
        node top=q.top();
        q.pop();
        int u=top.u;
        if(u==des)
            return d[des];
        for(int i=0;i<g[u].size();i++)
        {
            int v=g[u][i];
            if(d[u]+cost[u][v]<d[v])
            {
                d[v]=d[u]+cost[u][v];
                q.push(node(v,d[v]));
            }
        }
    }
    return -1;

}
int main()
{
    int t,edge_number,src,des,cas=1,u,v,delay,n;
    scanf("%d",&t);
    while(t--)
    {
        reset();
        scanf("%d %d %d %d",&n,&edge_number,&src,&des);
        for(int i=0;i<edge_number;i++)
        {
            scanf("%d %d %d",&u,&v,&delay);
            g[u].push_back(v);
            g[v].push_back(u);
            cost[u][v]=delay;
            cost[v][u]=delay;
        }
        int ret=dijkstra(n,src,des);
        if(ret==-1)
            printf("Case #%d: unreachable\n",cas);
        else
            printf("Case #%d: %d\n",cas,ret);
        cas++;
    }
}

Re: 10986 - Sending email

Posted: Sun Aug 04, 2013 10:11 am
by setu basak
above code give me TLE ..couldn't understand..

Re: 10986 - Sending email

Posted: Tue Aug 06, 2013 4:01 am
by brianfry713
I made a few optimizations to your code and got it AC in 1.6 seconds. Change reset to only clear g[0] through g[n - 1]. In dijkstra, only set d[0] through d[n - 1] to infinity.
All times are UTC+02:00
Page 4 of 5

Powered by phpBB® Forum Software © phpBB Limited