## 11857 - Driving Range

All about problems in Volume 118. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

durjay
New poster
Posts: 13
Joined: Tue Oct 06, 2009 5:09 pm
Location: ctg

### 11857 - Driving Range

I think this is simple DFS problem.
I called a dfs then check which road length is maximum
and then give the answer.....
Is my approach is ok?

PLZ give me some critical input output....

Thanx for advance help Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11857 - Driving Range

Read about MST (minimal spanning tree)!
wazaaaap
New poster
Posts: 7
Joined: Thu Sep 23, 2010 12:55 am

### Re: 11857 - Driving Range

I don't know why but I'm not able to understand those graph problems. Do you think i am the problem or problem description is not so good ? And can you give me some guide to improve the ability of understanding the problem.
Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11857 - Driving Range

Solve,solve and solve......
vermapratyush
New poster
Posts: 2
Joined: Mon Oct 04, 2010 4:59 pm

### Re: 11857 - Driving Range

In my code I have used prims algorithm to find MST. and the edge with maximum length is the output. I am getting TLE..
I submitted my solution without calling the function to find MST (func name is dfs) still i got TLE.. so i think the problem is in variable declaration (for adjacency matrix) very unlikely though.... which i have implemented using array of vectors to make a 2D array..
the input range was 1 million. are there any other alternative of making an adjacency matrix.

Code: Select all

``````
using namespace std;
#include <algorithm>
#include <iostream>
#include <iterator>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
//BEGIN_TEMPLATE_BY_PRATYUSH_VERMA

//CONSTANT
#define INF (1<<31)-1
#define PI 3.1428571428571428571428571428571

//FUNC
#define MAX(i,j) (i)>(j)?(i):(j)
#define MIN(i,j) (i)<(j)?(i):(j)
#define REP(i,a) for((i)=0;(i)<(a);(i)++)
#define REP_(i,a) for((i)=0;(i)<=(a);(i)++)
#define FOR(i,a,b) for((i)=(a);(i)<(b);(i)++)
#define FOR_(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define VAR(V,init) __typeof(init) V=(init)
#define FOREACH(I,C) for(VAR(I,(C).begin());I!=(C).end();I++)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((int)(x.size()))
#define LENGTH(x) ((int)(x.length()))
#define SZ(x) sizeof(x)
#define MEM(m,i) memset((m),(i),SZ(m))
#define PB(x,y) (x).push_back(y)
#define MP(x,y) make_pair(x,y)
#define V(x) vector < x >

typedef pair<int,int>   PII;
typedef pair<char,int>  PCI;
typedef pair<int,PII>   TRI;
typedef V( int )        VI;
typedef V( PII )        VII;
typedef V( TRI )        VTRI;
typedef V( string )     VS;
typedef long long       LL;
typedef long double     LD;

inline string i2s(int number) { stringstream ss; ss << number; return ss.str(); }
inline void input( int &n ) { n=0; int ch=getchar(); while( ch < '0' || ch > '9' ) ch=getchar(); while( ch >= '0' && ch <= '9' ) n = (n<<3)+(n<<1) + ch-'0', ch=getchar(); }
vector<int> adj;
bool vis;
int m,n;
//END_TEMPLATE_BY_PRATYUSH_VERMA

struct node {
int i;
node (int a) {i=a;}
friend bool operator< (const node &a, const node &b)
{
return (a.i>b.i);
}

};

int dfs()
{
int min=0;
priority_queue<node> s;
s.push(node (0));
int i;
while(!s.empty())
{
node t=s.top();
s.pop();
vis[t.i]=true;
REP(i,n)
{
if(vis[i]==true || t.i==i) continue;
if( adj[t.i][i]==-1) continue;
if(adj[t.i][i]>min) min=adj[t.i][i];
s.push(node (i));
}
}
REP(i,n)
if(!vis[i]) return -1;
return min;
}
int main()
{
int i,j,k,p,q;
while(1)
{
input(n);
input(m);
if(m==0 && n==0) return 0;
if(m<n-1)
{
printf("IMPOSSIBLE\n");
continue;
}
MEM(vis,0);
REP(i,n) adj[i].clear();
REP(i,n)
REP(j,n) PB(adj[i],-1);
REP(i,m)
{
input(p);
input(q);
input(k);
//            cin>>p>>q>>k;
if(adj[p][q]!=-1) k=min(k,min(adj[p][q],adj[q][p]));
adj[p][q]=k;
adj[q][p]=k;
}
int flag=dfs();
if(flag==-1) printf("IMPOSSIBLE\n");
else
{
printf("%d\n",flag);
}
}
return 0;
}
``````
Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11857 - Driving Range

Yes of course read about Kruskal algorithm!
Here you find a data that needed!
vermapratyush
New poster
Posts: 2
Joined: Mon Oct 04, 2010 4:59 pm

### Re: 11857 - Driving Range

ooh.. got it thanks.. durjay
New poster
Posts: 13
Joined: Tue Oct 06, 2009 5:09 pm
Location: ctg

### Re: 11857 - Driving Range

Now i got accepted but my runtime is 2.904 I use Kruskal + dfs.
can anyone give me any hints to decrease my runtime....
Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

### Re: 11857 - Driving Range

durjay wrote:Now i got accepted but my runtime is 2.904 I use Kruskal + dfs.
can anyone give me any hints to decrease my runtime....
I used Disjoint Sets to solve the problem. My running time is 0.684 sec.
Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

### Re: 11857 - Driving Range

getting wa pls help  Code: Select all

``````got ac code removed :)

``````
Last edited by Jehad Uddin on Thu Nov 04, 2010 7:57 am, edited 1 time in total.
MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

### Re: 11857 - Driving Range

HI In your link funtion return int But you return nothing

hope it help you....
shibly
New poster
Posts: 5
Joined: Wed Sep 22, 2010 7:32 am

### Re: 11857 - Driving Range

Hafiz in 67th line you used
if(u != v)
but it will be
if(x!=y)
Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

### Re: 11857 - Driving Range

thanks Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

### Re: 11857 - Driving Range

Sorry for Silly Post..I designed a way to solve this problem using DFS.But I dont know which data structure is to use for representing
the Graph.Because size is too much(1 million).I code in c/c++ but array,structure of c/c++ cant support this huge memory.So how to represent graph?  MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

### Re: 11857 - Driving Range

You can use adjacent list or structure ot STL container like as vector