### Distance in graph 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.
 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273`` ``````#include #include #include #include #include using namespace std; // C++ program to find minimum edge // between given two vertex of Graph #include using namespace std; // function for finding minimum no. of edge // using BFS int minEdgeBFS(vector edges[], int u, int v, int n) { // visited[n] for keeping track of visited // node in BFS vector visited(n, 0); // Initialize distances as 0 vector distance(n, 0); // queue to do BFS. queue 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[], 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 edges[n]; while(m--) {cin>>u>>v; addEdge(edges, u, v);} vectorD(n); for(auto &d:D) cin>>d; return 0; } `````` ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788`` ``````#include #include #include using namespace std; vector Dijkstra( const vector< vector > &Graph, int s ); //====================================================================== int main() { // Read number of nodes, number of edges, source node int n, m, s; cin >> n >> m >> s; vector< vector > 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 dist = Dijkstra( Graph, s ); // dist[] will contain value -1 if inaccessible // Maximum node at each distance vector 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 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 Dijkstra( const vector< vector > &Graph, int s ) { // Non-finalised nodes int n = Graph.size() - 1; set available; for ( int i = 1; i <= n; i++ ) available.insert( i ); available.erase( s ); // Initialise distance vector 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 Hi, I tried and it passed two test cases and got few wrong answers and terminated due to time out. Does this fix the wrong answers? (It won't fix the timeout.)

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788`` ``````#include #include #include #include using namespace std; vector Dijkstra( const vector< vector > &Graph, int s ); //====================================================================== int main() { // Read number of nodes, number of edges, source node int n, m, s; cin >> n >> m >> s; vector< vector > 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 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 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 queries( n ); for ( int &q : queries ) cin >> q; // Answer all queries for ( int q : queries ) cout << distances[q] << ' '; cout << '\n'; } //====================================================================== vector Dijkstra( const vector< vector > &Graph, int s ) { // Non-finalised nodes int n = Graph.size() - 1; set available; for ( int i = 1; i <= n; i++ ) available.insert( i ); available.erase( s ); // Initialise distance vector 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; } //====================================================================== `````` Hi it passed three test cases but there're still some wrong answers. Are the answers wrong ... or are they just timing out? Hi, I got two wrong answers and nine time out. 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?

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990`` ``````#include #include #include #include using namespace std; vector Dijkstra( const vector< vector > &Graph, int s ); //====================================================================== int main() { // Read number of nodes, number of edges, source node int n, m, s; cin >> n >> m >> s; vector< vector > 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 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 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 queries( n ); for ( int &q : queries ) cin >> q; // Answer all queries for ( int q : queries ) cout << distances[q] << ' '; cout << '\n'; } //====================================================================== vector Dijkstra( const vector< vector > &Graph, int s ) { int n = Graph.size() - 1; // Initialise distance vector 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,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 Hi lastchance, n and m can go up to 100000, and the updated code using priority queue passed all ten test cases, thanks! but do you understand both the code and the underlying algorithm
Topic archived. No new replies allowed.