OJ Board

i am stil getting WA even after considering graph as disconnected here is my code #include <iostream> #include <stdlib.h> #include <algorithm> #include <string.h> #include <sstream> #include <map> #include <vector> #define max 110 using namespace std; map<string,int> mp; vector<int> adj[max]; int di...

this is a irritating problem here is my code instead of checking all possible string set find all the edit steps of a string and apply binary search #include <iostream> #include <stdlib.h> #include <string.h> #include <map> #include <vector> #define max 26000 using namespace std; int dp[max]; vector...

#include<iostream> #include<stdio.h> #include<vector> #include<queue> #include<string.h> #include<algorithm> #include<iomanip> #define max 110 using namespace std; int n,e,sv,ev,x,y; float r,d,tmin; float dist[max]; int pred[max]; int status[max]; struct set { int parent; int rank; }; struct st { in...

#include<iostream> #include<stdio.h> #include<vector> #include<queue> #include<string.h> #include<algorithm> #include<iomanip> #define max 110 using namespace std; int n,e,sv,ev,x,y; float r,d,tmin; float dist[max]; int pred[max]; int status[max]; struct set { int parent; int rank; }; struct st { in...

#include<iostream> #include<stdio.h> #include<vector> #include<queue> #include<string.h> #include<algorithm> #define infinity 999999999 #define max 110 int cost; int table[max][max]; using namespace std; int t,n,m,c1,c2,d,sv; int status[max]; struct set { int parent; int rank; }; struct st { int u; ...

here u must not use adjacency matrix for representaiom use array of vectors because there can be more than one undirected edges bw two nodes first run dijkstra sssp with STL heap and get distances from node 2 create dag using dist[a]>dist in dag also u can have more than one edges between two nodes ...

i tried a lot using dijkstra and STL priority queue
had the lengths provided>0,there is nothing in problm
but in this case the code may get stuck into local loops and u ll get TLE
i used eppstein algorithm and got AC

i used dijkstra with heap
u can also use c++ stl priority queue
here is my AC code
http://ideone.com/EO771i

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

a cut edge or bridge edge is not the part of any cycle so for each edge u-v if there exists any desecdant of v (inclusive) which has a back edge on the ancestors of u (inclusive) then that edge is not back edge http://ideone.com/rpPQdQ i m getting WA need hellp.... need to know wat AC soln gives for...

here u have to travel all the vertices
but in bfs tree where there a branching occurs then return the max depth incurred bcoz by that tym other fleet would have completed the other branch
so u just find the max(dist[root]+dist[s]) after floyd warshall

dp is usefull only when knapsack capacity is not too large
here in worst case W=100*500
how dp can be usefull here

the problem doesnt have the optimal substructure property so how can one use greedy algorithm(dijkstra),
i think we can modify dijkstra algo by keeping track of the minimum distance from both economical and express rails
and then we can find shortest route

it is an application of floyd warshal algo
finding the minimax path.
here we have to minimise the maximum edge value in all path
for(k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[j]=min(dp[j],max(dp[k],dp[k][j])

the question is simply a modification of floyd warshal algo for maximin path a maximin path =we maximise the path in which edge length is minimum for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) dist [j]=max(dist [j],min(dist [k],dist[k][j]) http://ideone.com/Gjv9Bo is my AC code :roll: