C++

Forum

 
Distance in graph

Pen72 (74)
Nodes are indexed by positive integers from 1 ton .

Each edge is represented by (u,v) connecting node u and node v .

Distance of two nodes, say x and y, is defined as number of edges on the shortest path between x and y, if x and y are reachable from each other; otherwise, it is defined as 0.

There is a reference node s, and a special query Max Index (d), which is defined as maximal index of node among nodes whose distance to s is d.

If there is no node whose distance to s is d, Max Index(d)is defined as 0 .

Our task is to respond a sequence of n queries, D=di(i=1~n).

Input Format

The 1st line is n, m and s .
The following m lines are edges.
The following line is D.

Output Format
Max Index(di)

Sample Input 0

6 7 1
1 2
1 3
2 3
2 4
3 5
4 5
4 6
2 1 3 1 2 3
Sample Output 0

5 3 6 3 5 6

How can this problem be solved, I don't think I'm on the right path.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

// C++ program to find minimum edge
// between given two vertex of Graph
#include<bits/stdc++.h>
using namespace std;
 
// function for finding minimum no. of edge
// using BFS
int minEdgeBFS(vector <int> edges[], int u,
                              int v, int n)
{
    // visited[n] for keeping track of visited
    // node in BFS
    vector<bool> visited(n, 0);
 
    // Initialize distances as 0
    vector<int> distance(n, 0);
 
    // queue to do BFS.
    queue <int> Q;
    distance[u] = 0;
 
    Q.push(u);
    visited[u] = true;
    while (!Q.empty())
    {
        int x = Q.front();
        Q.pop();
 
        for (int i=0; i<edges[x].size(); i++)
        {
            if (visited[edges[x][i]])
                continue;
 
            // update distance for i
            distance[edges[x][i]] = distance[x] + 1;
            Q.push(edges[x][i]);
            visited[edges[x][i]] = 1;
        }
    }
    return distance[v];
}
 
// function for addition of edge
void addEdge(vector <int> edges[], int u, int v)
{
   edges[u].push_back(v);
   edges[v].push_back(u);
}
 

int main()
{
    int n,m,s,u,v;
    cin>>n>>m>>s;
    vector <int> edges[n];
    while(m--)
    {cin>>u>>v;
     addEdge(edges, u, v);}
    vector<int>D(n);
    for(auto &d:D) cin>>d;

    return 0;
}

lastchance (6980)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
#include <iostream>
#include <vector>
#include <set>
using namespace std;

vector<int> Dijkstra( const vector< vector<int> > &Graph, int s );

//======================================================================

int main()
{
   // Read number of nodes, number of edges, source node
   int n, m, s;
   cin >> n >> m >> s;
   vector< vector<int> > Graph( 1 + n );         // Forget node 0; can't cope with zero-based!

   // Read edges
   for ( int i = 1; i <= m; i++ )
   {
      int a, b;
      cin >> a >> b;
      Graph[a].push_back( b );
      Graph[b].push_back( a );
   }

   // Find minimum distances from source
   vector<int> dist = Dijkstra( Graph, s );      // dist[] will contain value -1 if inaccessible

   // Maximum node at each distance
   vector<int> distances( 1 + n, -1 );
   for ( int i = 0; i <= n; i++ )
   {
      int d = dist[i];
      if ( d >= 0 && distances[d] < i ) distances[d] = i;
   }

   // Read all queries
   vector<int> queries( n );
   for ( int &q : queries ) cin >> q;

   // Answer all queries
   for ( int q : queries )
   {
      if ( distances[q] <= 0 ) cout << 0 << ' ';
      else                     cout << distances[q] << ' ';
   }
   cout << '\n';
}

//======================================================================

vector<int> Dijkstra( const vector< vector<int> > &Graph, int s )
{
   // Non-finalised nodes
   int n = Graph.size() - 1;
   set<int> available;
   for ( int i = 1; i <= n; i++ ) available.insert( i );
   available.erase( s );

   // Initialise distance
   vector<int> dist( 1 + n, -1 );                          // -1 means inaccessible
   dist[s] = 0;

   // Consider all distances from the most-recently-finalised node
   while( !available.empty() )
   {
      // Update new distances from most-recently-finalised node
      int newDist = dist[s] + 1;
      for ( auto t : Graph[s] ) if ( dist[t] < 0 || dist[t] > newDist ) dist[t] = newDist;

      // Find smallest distance in available nodes; finalise that node
      s = *available.begin();
      int distmin = dist[s];
      for ( int a : available )
      {
         if ( dist[a] >= 0 && dist[a] < distmin )
         {
            s = a;
            distmin = dist[a];
         }
      }
      available.erase( s );                                // Finalise by removing
   }

   return dist;
}

//====================================================================== 


5 3 6 3 5 6

Last edited on
Pen72 (74)
Hi, I tried and it passed two test cases and got few wrong answers and terminated due to time out.
lastchance (6980)
Does this fix the wrong answers? (It won't fix the timeout.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

vector<int> Dijkstra( const vector< vector<int> > &Graph, int s );

//======================================================================

int main()
{
   // Read number of nodes, number of edges, source node
   int n, m, s;
   cin >> n >> m >> s;
   vector< vector<int> > Graph( 1 + n );         // Forget node 0; can't cope with zero-based!

   // Read edges
   for ( int i = 1; i <= m; i++ )
   {
      int a, b;
      cin >> a >> b;
      Graph[a].push_back( b );
      Graph[b].push_back( a );
   }

   // Find minimum distances from source
   vector<int> dist = Dijkstra( Graph, s );      // dist[] will contain value -1 if inaccessible

   // This is silly ... but accords with the question
   replace( dist.begin(), dist.end(), -1, 0 );

   // Maximum node at each distance
   vector<int> distances( 1 + n, 0 );
   for ( int i = 0; i <= n; i++ )
   {
      int d = dist[i];
      if ( distances[d] < i ) distances[d] = i;
   }

   // Read all queries
   vector<int> queries( n );
   for ( int &q : queries ) cin >> q;

   // Answer all queries
   for ( int q : queries ) cout << distances[q] << ' ';
   cout << '\n';
}

//======================================================================

vector<int> Dijkstra( const vector< vector<int> > &Graph, int s )
{
   // Non-finalised nodes
   int n = Graph.size() - 1;
   set<int> available;
   for ( int i = 1; i <= n; i++ ) available.insert( i );
   available.erase( s );

   // Initialise distance
   vector<int> dist( 1 + n, -1 );                          // -1 means inaccessible
   dist[s] = 0;

   // Consider all distances from the most-recently-finalised node
   while( !available.empty() )
   {
      // Update new distances from most-recently-finalised node
      int newDist = dist[s] + 1;
      for ( auto t : Graph[s] ) if ( dist[t] < 0 || dist[t] > newDist ) dist[t] = newDist;

      // Find smallest distance in available nodes; finalise that node
      s = *available.begin();
      int distmin = dist[s];
      for ( int a : available )
      {
         if ( dist[a] >= 0 && dist[a] < distmin )
         {
            s = a;
            distmin = dist[a];
         }
      }
      available.erase( s );                                // Finalise by removing
   }

   return dist;
}

//======================================================================

Pen72 (74)
Hi it passed three test cases but there're still some wrong answers.
lastchance (6980)
Are the answers wrong ... or are they just timing out?
Pen72 (74)
Hi, I got two wrong answers and nine time out.
lastchance (6980)
Maybe try Dijkstra's algorithm with a priority queue.

Can you report, please, how many:
- correct
- wrong
- timed out
and any other feedback that your tester gives you. I haven't managed to create any graphs, connected or otherwise, where it actually gives the wrong answer. Dijkstra's algorithm and handling the adjacency information are the only things in the code that aren't O(N).

How big can n and m get?


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> Dijkstra( const vector< vector<int> > &Graph, int s );

//======================================================================

int main()
{
   // Read number of nodes, number of edges, source node
   int n, m, s;
   cin >> n >> m >> s;
   vector< vector<int> > Graph( 1 + n );         // Forget node 0; can't cope with zero-based!

   // Read edges
   for ( int i = 1; i <= m; i++ )
   {
      int a, b;
      cin >> a >> b;
      Graph[a].push_back( b );
      Graph[b].push_back( a );
   }

   // Find minimum distances from source
   vector<int> dist = Dijkstra( Graph, s );                // dist[] will be -1 if inaccessible

   // This is silly ... but accords with the question
   replace( dist.begin(), dist.end(), -1, 0 );

   // Maximum node at each distance
   vector<int> distances( 1 + n, 0 );
   for ( int i = 0; i <= n; i++ )
   {
      int d = dist[i];
      if ( distances[d] < i ) distances[d] = i;
   }

   // Read all queries
   vector<int> queries( n );
   for ( int &q : queries ) cin >> q;

   // Answer all queries
   for ( int q : queries ) cout << distances[q] << ' ';
   cout << '\n';
}

//======================================================================

vector<int> Dijkstra( const vector< vector<int> > &Graph, int s )
{
   int n = Graph.size() - 1;

   // Initialise distance
   vector<int> dist( 1 + n, -1 );                          // -1 means inaccessible
   dist[s] = 0;

   // Create a priority queue that will be sorted by distance from source
   auto further = [&]( int a, int b ){ return dist[b] < 0 || dist[a] > dist[b]; };
   priority_queue<int,vector<int>,decltype(further)> Q( further );

   // Push all nodes accessible from the start onto the queue
   for ( int e : Graph[s] )
   {
      dist[e] = 1;
      Q.push( e );
   }   

   // Take the smallest distance amongst those so far accessible and pop it from the top of the queue.
   while( !Q.empty() )
   {
      s = Q.top();
      Q.pop();
      for ( int e : Graph[s] )
      {
         int test = dist[s] + 1;
         if ( dist[e] < 0 || dist[e] > test )        // If we improve a distance, then push onto queue
         {
            dist[e] = test;
            Q.push(e);
         }
      }
   }

   return dist;
}

//======================================================================

Last edited on
Pen72 (74)
Hi lastchance, n and m can go up to 100000, and the updated code using priority queue passed all ten test cases, thanks!
seeplus (6591)
but do you understand both the code and the underlying algorithm
Topic archived. No new replies allowed.