11857 - Driving Range

[Imti]

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..

[mahade hasan]

why every time get submission error

[brianfry713]

Try a different problem

[Saminur Islam]

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]

That is AC code.

[brianfry713]

Input:

Code: Select all

3 1
0 1 1
0 0

AC output IMPOSSIBLE

[sreka11]

ACC