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

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

Re: 11857 - Driving Range

Post by Imti » Thu May 19, 2011 9:36 pm

Thanks MRH..Actually I just checked this thread today..And I got it Accepted...with runtime of 0.616 sec..My initial approach might be right (with dfs),there is no need of dfs at all..disjoint-forest of course with kruskal could handle all about it effectively.. :) :)

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 11857 - Driving Range

Post by mahade hasan » Tue Jun 11, 2013 12:01 am

why every time get submission error :oops: :oops: :oops:
we r surrounded by happiness
need eyes to feel it!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11857 - Driving Range

Post by brianfry713 » Tue Jun 11, 2013 12:35 am

Try a different problem
Check input and AC output for thousands of problems on uDebug!

Saminur Islam
New poster
Posts: 4
Joined: Tue Dec 10, 2013 10:49 am

Re: 11857 - Driving Range

Post by Saminur Islam » Tue Dec 10, 2013 12:35 pm

Everytime I am getting submission error...... i dont understand why submission error.....plz help me to find out my problem with this code

Code: Select all

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
using namespace std;
#define max(a,b) (a>b)?a:b
vector< pair<int,pair<int,int> >  > Edge;
int M,N,d;
bool visited[1000001];
int pset[1000001];

int find(int V)
{
    if(pset[V] == V)
		return V;
	else
		return (pset[V] = find(pset[V]));
}
void union_find(int u,int v)
{
    pset[find(u)] = find(v);
}

bool comp(pair<int,pair<int,int> > edge1,pair<int,pair<int,int> >edge2)
{
    pair<int,int> p1;
    pair<int,int>p2;
    p1=edge1.second;
    p2=edge2.second;
    return p1.second<p2.second;
}
int kruskal()
{
    int i,lweight;
    int m;
    memset(visited,false,sizeof visited);
    sort(Edge.begin(),Edge.end(),comp);
    int totalcost=0;
    d=0;
    m=0;
    for(i=0;i<Edge.size();i++)
    {
        pair<int,pair<int,int> > p=Edge[i];
        pair<int,int> q=p.second;
        int V1=p.first;
        int V2=q.first;
        if((find(V1)!=find(V2)))
        {
            //cout<<V1<<"-"<<V2<<":"<<q.second<<endl;
            d++;
            lweight=q.second;
            totalcost+=q.second;
            visited[i]=true;
            union_find(find(V1),find(V2));
            m = max(m,q.second);
        }
    }
    //cout<<"Total Cost: "<<totalcost<<endl;
    return lweight;
}

int main()
{
    //freopen("i.txt","r",stdin);
    int i,j,k;
    int value1,value2,weight;
    while(scanf("%d %d",&N,&M)==2)
    {
        if(N==0&&M==0) break;
        Edge.clear();
        for(j=0;j<N;j++)
        {
            pset[j]=j;
        }
        for(i=0;i<M;i++)
        {
            scanf("%d %d %d",&value1,&value2,&weight);
            Edge.push_back(make_pair(value1,make_pair(value2,weight)));
        }
        int totalcost=kruskal();
        if(d<N-1)
        {
            cout<<"IMPOSSIBLE"<<endl;
        }
        else
        {
            cout<<totalcost<<endl;
        }
    }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11857 - Driving Range

Post by brianfry713 » Tue Dec 10, 2013 10:29 pm

That is AC code.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11857 - Driving Range

Post by brianfry713 » Wed Aug 27, 2014 7:19 pm

Input:

Code: Select all

3 1
0 1 1
0 0
AC output IMPOSSIBLE
Check input and AC output for thousands of problems on uDebug!

sreka11
New poster
Posts: 15
Joined: Fri Aug 15, 2014 8:06 pm

Re: 11857 - Driving Range

Post by sreka11 » Sat Sep 20, 2014 12:41 pm

ACC

Post Reply

Return to “Volume 118 (11800-11899)”