10986 - Sending email

[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.

[DD]

Hello People.

Follow some test cases to the problem (test using uva tookit: http://uvatoolkit.com/problemssolve.php)
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

[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;
}

[shanto_0321]

if we scan a='0',then why we do not get the value of a=48-'0'=0.
what is the problem.
#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;
}

[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

[brianfry713]

Doesn't match the sample I/O.

[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.

[brianfry713]

I used a C++ STL priority_queue in Dijkstra's algorithm. Is your queue logarithmic?

[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;
}



[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.

[mahade hasan]

cut after AC.....