Page 2 of 2

Re: 10462 - Is There A Second Way Left ?

Posted: Fri Feb 27, 2009 10:31 pm
by Chirag Chheda
Well Initially I got several WA for this prob but later i found a case which my code was not handling properly which helped me 2 get an ACC. Hope it helps u.

Input:

Code: Select all

1
3 4
1 2 1
1 2 1
2 3 1
2 3 1
Output is 2 obviously.

Re: 10462 - Is There A Second Way Left ?

Posted: Sat Feb 28, 2009 1:15 pm
by pradeepr
Thanks for your help
But my code gives the same answer as u have mentioned for the above input.. though the online judge gives a WA

Re: 10462 - Is There A Second Way Left ?

Posted: Sun Mar 01, 2009 12:49 pm
by Chirag Chheda
Well in that case it would be better if u post ur code and explain ur algo.
Thanx.

Re: 10462 - Is There A Second Way Left ?

Posted: Mon Mar 09, 2009 3:38 pm
by pradeepr
hey.. thanks for the help..my code is attached in my first post in the previous page.Please go through it .My algo also has been briefly explained there though I would like to explain in detail.

I am using kruska's algorithm to find the MST.If the number of components after running kruskals is greater than 1,then there exists no MST and I output the result accordingly.
if MST exists,then I look for 2nd minimum spanning tree.I used the algorithm suggested in cormen for this.
all the edges (u,v) part of the graph and not present in the MST will be added to the MST one at a time and the maximum edge on the resultant cycle is removed.This operation make the resultant structure a tree.
Of all such possibles trees ,I choose the tree with minimum weight sum.


Please go through my code ang suggest me something as to what is wrong with it.

Code: Select all

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstdio>
#include<map>
#include<vector>
using namespace std;
typedef struct node
{
        struct node* head; //head of the disjoint set
        struct node* next; // next node of the disjoint set
        int label;
}node;

typedef struct edge
{
        int inlabel; //invertex label
        int outlabel;//outvertex label
        int weight;   //weight of the edge
        bool belongs; //indicates whether it belongs to MST or not
}edge;



void make_set(node &N) // makes a single node disjoint set
{
        N.head=&N;
        N.next=NULL;
}

node * find_set(node N) // returns the head of the list in which the node N is placed
{

        return N.head;
}

void find_union(node *a, node *b,map<node*,node*> &M) //union of 2 disjoint sets given their heads
{
        node *tail1=M[a];
        tail1->next=b;
        M.erase(b);
        while(b->next !=NULL)
        {
                b->head=a;
                b=b->next;
        }
        b->head=a;
        M[a]=b;
}


int compare(const void *a,const void *b) // compare function to sort the edges based on their weights
{
	edge x=*(edge*)a;
	edge y=*(edge*)b;
	if(x.weight >  y.weight)
		return 1;
	else
		return -1;
}

void DFS_FILL_MAX_VISIT(int u,int x,int size,int **G,vector<int>& max) // find an edge of max weight on the unique path  from u to every vertex v and stores it in max[v]
{
	for(int v=0;v<size;v++)
	{
		if( G[x][v]>0 && max[v]==0 && v!=u)
		{

			if(x==u ||( G[x][v] >max[x]))
				max[v]=G[x][v];
			else
				max[v]=max[x];

			DFS_FILL_MAX_VISIT(u,v,size,G,max);
		}
	}
}


int main()
{
	int num_cases,N,num_edges;
	int temp1,temp2;
	int temp3;
	cin >>num_cases;
	for(int k=0;k<num_cases;k++)
	{
		cin>>N;
		unsigned long w=0,w2=1000000;
		node *vertices=new node[N];
		cin>>num_edges;
		edge *edges=new edge[num_edges];

		map<node*,node*> M;
		node *head1,*head2;

		int ** G= new int*[N]; //MST to be built 
		for(int i=0;i<N;i++)
		{
			G[i]=new int[N];
			for(int j=0;j<N;j++)	//initialization.. an edge G[i][j]=0 implies there is no edge between vertices i and j
				G[i][j]=0;
		}	
		                  //using kruskals algorithm to build a MST
		for(int j=0;j<N;j++)
		{
			(vertices[j]).label=j;
			M[vertices+j]=vertices+j;  //linked list representation in which the map M is used to find the tail of list given the head  i.e M[head]=tail
			make_set(vertices[j]);      

		}

		temp3=0;
		for(int j=0;j<num_edges;j++)
		{
			cin>>temp1>>temp2>>temp3;
			edges[j].inlabel=temp1-1;
			edges[j].outlabel=temp2-1;
			edges[j].weight=temp3;
			edges[j].belongs=false;

		}
		qsort(edges,num_edges,sizeof(edge),compare);

		for(int j=0;j<num_edges;j++)
		{
			head1=find_set(vertices[edges[j].inlabel]);
			head2=find_set(vertices[edges[j].outlabel]);
			if(head1!=head2)
			{
				find_union(head1,head2,M);
				w+=edges[j].weight;
				edges[j].belongs=true;
				G[edges[j].outlabel][edges[j].inlabel]=G[edges[j].inlabel][edges[j].outlabel]=edges[j].weight;
			}
		}
		cout<<"Case #"<<k+1<<" : ";
		if(M.size()>1)
			cout<<"No way";
		else 
		{

			w2=1000000;
			for(int j=0;j<num_edges;j++)
			{
				int u,v;
				if(!edges[j].belongs)
				{
					vector<int> temp(N,0);
					u=edges[j].inlabel;
					v=edges[j].outlabel;
					DFS_FILL_MAX_VISIT(u,u,N,G,temp);
					if( (edges[j].weight-temp[v])< w2)
					{
						w2=(edges[j].weight-temp[v]);
					}
				}
			}
			if(w2==1000000)
				cout<<"No second way";
			else
				cout<<w+w2;
		}
			cout<<'\n';
	}
	return(0);
}


Re: 10462 - Is There A Second Way Left ?

Posted: Mon Mar 09, 2009 6:50 pm
by Chirag Chheda
all the edges (u,v) part of the graph and not present in the MST will be added to the MST one at a time and the maximum edge on the resultant cycle is removed.This operation make the resultant structure a tree.
I doubt if your this part is correct or not. However I can tell you my algo for the second part. Remove one edge at a time from the above MST and then find the value of the resulting MST. After doing this for all the edges present in the first MST find the one with the minimum value.

Hope it helps.

Re: 10462 - Is There A Second Way Left ?

Posted: Tue Mar 10, 2009 3:31 pm
by pradeepr
This one was same as the problem 10600.My algo was the same for both and my solution for 10600 got accepted.
I followed the algo give in cormen to generate the second MST.
Please post some input cases that might be crucial in judging where my solution goes wrong.

Re: 10462 - Is There A Second Way Left ?

Posted: Sat Oct 03, 2009 2:01 am
by Jehad Uddin
Try this cases,
Input

Code: Select all

2
8 7
1 2 1
2 3 2
3 4 4
4 5 5
5 6 7
6 7 8
7 8 9
3 5
1 2 3
2 3 1
2 2 4
1 1 5
2 3 5


Output

Code: Select all

Case #1 : No second way
Case #2 : 8

Re: 10462 - Is There A Second Way Left ?

Posted: Sun Mar 25, 2012 7:39 pm
by Raihan92
Why WA??? Need some test cases why wrong...totally confused :o :roll:

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<cstdlib>
#define MAXS 10600
#define INFINITY 100000000
using namespace std;
#define REP(i,n) for (i=0;i<n;i++)
#define PI (2*acos(0))
#define ERR 1e-5
#define mem(a,b) memset(a,b,sizeof a)
#define pb push_back

struct airport
{
    int x,y,cost;
};

airport EDGE[MAXS];
int find_representative(int r);
bool compare(const airport& a, const airport& b);
int parent[MAXS],CMST[MAXS];
bool mark[MAXS];

int main()
{
    int i,j,k,l,t,u,v,RE_F1,RE_F2,TEST,N,M,T_COST,temp,sum,MIN,A,B;
    scanf("%d",&TEST);
    for(t=1; t<=TEST; t++)
    {
        memset(parent,0,sizeof(parent));
        memset(EDGE,0,sizeof(EDGE));
        memset(mark,0,sizeof(mark));
        memset(CMST,0,sizeof(CMST));
        scanf("%d %d",&N,&M);
        if(N==0&&M==0)
        {
            printf("Case #%d : No way\n",t);
            continue;
        }
        for(i=1; i<=M; i++)
        {
            scanf("%d %d %d",&EDGE[i].x,&EDGE[i].y,&EDGE[i].cost);
            //printf("%d %d %d\n",EDGE[i].x,EDGE[i].y,EDGE[i].cost);
        }
        A = M + 1;
        sort(EDGE,EDGE+A,compare);

        for(i=1; i<=N; i++)
            parent[i] = i;

        sum = 0;
        T_COST = 0;
        k = 1;

        for(i=1; i<=M; i++)
        {
            u = EDGE[i].x;
            v = EDGE[i].y;
            RE_F1 = find_representative(u);
            RE_F2 = find_representative(v);

            if(RE_F1!=RE_F2)
            {
                parent[RE_F1] = RE_F2;
                sum += EDGE[i].cost;
                mark[i] = true;
            }
        }

        B = parent[1];

        for(i=2; i<=N; i++)
        {
            if(B!=parent[i]&&M!=1)
            {
                sum = INFINITY;
            }
        }

        for(i=1; i<=M; i++)
        {
            if(mark[i]==true)
            {
                for(l=1; l<=N; l++)
                    parent[l] = l;

                for(j=1; j<=M; j++)
                {
                    if(j!=i)
                    {
                        u = EDGE[j].x;
                        v = EDGE[j].y;
                        RE_F1 = find_representative(u);
                        RE_F2 = find_representative(v);

                        if(RE_F1!=RE_F2)
                        {
                            //cout<<EDGE[j].cost<<endl;
                            parent[RE_F1] = RE_F2;
                            T_COST += EDGE[j].cost;
                        }
                    }
                }
                //cout << T_COST << endl;
                CMST[k] = T_COST;
                k++;
                T_COST = 0;
                mark[i] = true;
            }
        }
        k--;
        MIN = INFINITY;
        for(i=1; i<=k; i++)
        {
            if(CMST[i]<MIN&&sum<=CMST[i]) MIN = CMST[i];
        }
        if(MIN==INFINITY&&sum==INFINITY) printf("Case #%d : No way\n",t);
        else if(MIN==INFINITY&&sum!=INFINITY) printf("Case #%d : No second way\n",t);
        else printf("Case #%d : %d\n",t,MIN);
    }
    return 0;
}
bool compare(const airport& a, const airport& b)
{
    return a.cost < b.cost;
}

int find_representative(int r)
{
    if(parent[r]==r)
        return r;
    else
    {
        return parent[r] = find_representative(parent[r]);
    }
}



Re: 10462 - Is There A Second Way Left ?

Posted: Tue Mar 27, 2012 11:58 pm
by brianfry713
Try the input in the post before yours.

WA: 10462 - Is There A Second Way Left ?

Posted: Wed Feb 12, 2014 5:19 pm
by raihan_sust05
getting WA!!! :cry: pls anyone help me .....here is my code :

Code: Select all

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>


#define pi acos(0)
#define inf 20000000000
#define max 10000
#define sz 100
#define true 1
#define false 0
#define pb(a) push_back(a)
#define size(e) (int)e.size()
#define clr(a,b) memset(a,b,sizeof(a))

//ll rw[10] = {0,0,1,-1};
//ll cl[10] = {1,-1,0,0};   /*array for 4-sides move*/

//ll drw[10] = {1,-1,1,-1};
//ll dcl[10] = {1,1,-1,-1}; /*array for diagonal 4-sides move*/

//ll rw[10] = {0,0,1,1,-1,-1};
//ll cl[10] = {1,-1,1,0,-1,0};   /*array for 6-sides move*/

//ll rw[10] = {0,0,1,1,1,-1,-1,-1};
//ll cl[10] = {1,-1,1,0,-1,-1,0,1};   /*array for 8-sides move*/

//ll rw[10] = {0,0,1,-1, 0, 0};
//ll cl[10] = {1,-1,0,0, 0, 0};
//ll hi[10] = {0, 0 ,0, 0, 1, -1}; /*array for 3-D move */

typedef long long int ll;

struct edge
{
    ll u, v, c;

    bool operator <(const edge& p)const
    {
        return c < p.c;
    }
};



using namespace std;

ll num, m, par[max], mcost, scost, costs[max], got[max];
vector <edge> e;

ll mst();
ll omst(ll a);
ll find(ll a);

int  main()
{
    ll i, j, n, cas = 1, tst;
    edge bin;

    scanf("%lld", &tst);

    while(cas <= tst)
    {
        e.clear();
        clr(got, 0);

        scanf("%lld %lld", &num, &m);

        for(i = 0; i < m; ++i)
        {
            scanf("%lld %lld %lld", &bin.u, &bin.v, &bin.c);
            e.pb(bin);

        }

        mcost = 0;

        for(i = 1; i <= num; ++i)
            par[i] = i;

        for(i = 0; i < size(e); ++i)
        costs[i] = inf;

        ll c = 0;

        c =  mst();

        printf("Case #%lld : ", cas);

        scost = 0;

        if(c == num - 1)
        {
            n = 0;

            for(i = 0; i < size(e); ++i)
            {
                for(j = 1; j <= num; ++j)
                    par[j] = j;

                if(got[i])
                {
                    costs[i] = 0;
                    c = omst(i);

                    if(c < num - 1 || costs[i] < mcost)
                        costs[i] = inf;

                    if(c == num - 1 && costs[i] >= mcost)
                        ++n;
                }
            }

              if(n == 0)
                puts("No second way");

              else
               {
                 scost = *min_element(costs, costs + m);
                 printf("%lld\n", scost);
               }
        }

            else
            puts("No way");

            ++cas;
        }
        return 0;
}

    ll mst()
    {
        ll i, j, n, p;
        ll c = 0;

        sort(e.begin(), e.end());

        for(i = 0 ; i < size(e); ++i)
        {
            ll u = find(e[i].u);
            ll v = find(e[i].v);

            if(u != v)
            {
                par[v] = u;
                ++c;

                got[i] = true;

                mcost += e[i].c;

                if(c == num - 1)
                    break;

            }
        }

        return c;
    }

    ll omst(ll a)
    {
        ll i, j, n, p;
        ll c = 0;

        sort(e.begin(), e.end());

        for(i = 0 ; i < size(e); ++i)
        {
            ll u = find(e[i].u);
            ll v = find(e[i].v);

            if(u != v && i != a)
            {
                par[v] = u;
                ++c;

                costs[a] += e[i].c;

                if(c == num - 1)
                    break;

            }

        }

        return c;
    }

    ll find(ll a)
    {
        if(par[a]== a)
            return(a);

        return(par[a] = find(par[a]));
    }

Re: 10462 - Is There A Second Way Left ?

Posted: Wed Feb 12, 2014 9:34 pm
by brianfry713
Input:

Code: Select all

20
60 165
16 21 298
40 5 805
11 59 81
37 40 823
35 19 180
33 28 874
25 43 85
18 39 215
10 37 307
29 42 393
41 4 585
45 34 394
35 13 27
14 58 380
33 52 872
52 55 69
26 5 869
5 37 206
33 9 973
15 60 711
18 55 960
44 57 83
48 46 901
45 29 942
28 49 398
15 42 435
11 52 448
48 18 922
48 1 538
39 45 663
33 58 108
29 43 482
6 4 658
34 8 27
22 18 103
56 59 67
47 32 792
5 30 742
57 24 753
42 50 512
39 31 412
13 21 728
16 46 853
16 6 504
33 2 372
31 10 708
54 40 582
15 13 863
38 24 445
28 31 301
50 7 833
2 8 689
47 36 953
44 54 525
45 45 346
55 57 195
26 49 817
30 27 660
54 1 334
16 23 69
14 35 527
21 8 506
57 54 488
50 47 511
26 47 912
22 11 483
10 5 603
28 45 133
28 40 124
51 12 640
17 3 262
24 35 714
9 60 411
47 11 899
25 5 680
35 27 817
40 44 708
24 26 934
3 29 358
6 18 114
60 21 505
26 30 362
25 8 756
27 25 637
23 32 842
50 55 785
33 40 282
50 27 530
18 33 187
27 6 590
40 22 876
9 45 192
16 24 734
33 12 680
4 38 849
58 28 844
30 45 146
56 41 50
28 53 379
25 59 256
46 10 13
31 21 221
46 50 283
57 43 302
34 2 175
54 36 273
38 7 412
19 2 300
11 46 871
9 40 862
10 60 698
23 51 573
12 50 851
46 5 977
39 44 586
15 18 903
13 50 19
7 50 599
52 38 791
23 44 162
14 15 303
4 32 89
54 2 92
50 26 666
26 39 560
43 17 242
32 48 247
22 56 411
51 15 473
34 43 502
49 4 446
20 34 626
13 26 645
39 21 94
9 1 347
25 19 889
12 44 682
59 21 137
13 12 247
48 38 882
43 27 593
16 30 768
33 28 670
53 11 149
45 43 874
55 33 118
30 13 95
50 24 895
1 41 115
39 55 547
57 43 43
26 11 908
45 50 609
47 42 549
30 11 774
54 33 843
6 26 999
21 15 487
1 2 411
48 45 932
22 16 552
33 20 718
14 40 744
55 23 586
58 51 717
66 79
54 21 77
56 36 958
49 31 423
46 1 313
38 10 131
6 50 302
35 28 70
49 5 138
6 64 756
49 13 527
4 22 450
37 56 62
1 7 161
66 10 671
9 64 802
58 23 485
17 26 886
20 43 30
15 27 450
27 37 587
46 37 900
33 20 681
37 58 431
45 12 67
40 11 715
63 46 424
22 17 623
62 25 639
23 14 447
59 7 362
27 47 56
46 24 607
37 36 352
48 48 333
57 57 245
36 8 910
50 15 937
9 37 397
20 11 500
24 66 621
5 10 977
26 2 706
61 22 563
40 14 16
30 49 810
36 57 52
48 59 921
16 14 299
25 30 910
22 1 511
31 32 381
30 21 108
51 54 683
63 58 918
45 43 187
33 16 589
23 22 545
34 11 678
61 9 628
61 23 531
24 61 440
43 37 30
30 37 291
21 31 572
63 62 898
10 55 203
31 15 398
42 23 728
48 44 660
4 23 314
65 23 0
33 53 77
3 45 559
31 22 698
25 60 202
13 11 570
26 57 855
46 58 355
23 25 372
33 176
6 28 363
17 24 196
4 23 369
18 26 214
20 23 631
19 12 635
25 25 533
26 15 139
3 27 854
26 14 227
18 25 606
8 21 985
31 3 440
23 30 144
10 12 236
22 19 531
11 2 395
25 7 494
16 1 948
29 20 774
18 21 105
5 25 320
7 14 878
2 2 39
11 7 939
29 30 803
29 5 835
2 4 249
3 27 678
20 18 297
7 2 147
31 2 901
9 11 133
8 15 215
12 8 359
9 6 576
13 26 121
15 22 908
8 8 764
23 6 854
25 33 785
26 8 162
1 21 971
15 3 339
20 21 102
25 14 807
17 1 362
4 16 473
9 33 705
14 16 624
11 19 75
17 25 163
2 29 208
4 3 87
22 18 220
33 9 855
32 8 173
14 17 12
11 8 620
27 3 364
12 23 232
3 30 373
29 29 376
30 26 685
14 4 895
20 1 674
27 19 288
10 20 550
15 24 56
18 1 880
5 24 255
2 21 277
28 1 179
21 13 931
24 28 872
23 31 795
8 32 506
27 30 57
15 9 923
15 30 805
3 10 19
22 33 332
22 23 595
33 8 325
27 21 301
23 13 433
21 23 884
15 23 517
24 33 35
18 25 368
27 33 259
24 11 250
13 23 95
19 30 170
6 21 158
16 3 644
3 5 611
26 16 37
25 16 855
16 32 117
14 27 396
24 23 255
12 6 664
6 9 489
26 11 43
27 7 818
31 24 988
12 27 438
27 11 848
24 18 829
15 7 875
4 20 316
8 22 866
16 4 426
27 3 13
31 8 619
21 26 986
12 13 377
22 26 619
4 28 126
8 12 578
28 8 923
14 27 99
17 24 205
20 24 791
25 14 12
17 31 515
27 12 599
17 2 303
11 16 170
21 23 700
28 9 905
21 29 732
9 24 845
30 1 421
10 33 196
5 31 297
16 12 91
15 5 327
31 20 231
18 5 944
24 30 337
19 15 419
7 13 745
7 25 740
6 24 107
1 13 466
11 15 493
15 10 253
1 21 367
3 8 340
33 15 751
14 14 211
24 31 821
15 23 476
3 9 656
14 3 374
28 32 143
4 10 635
24 3 461
32 22 791
11 25 396
23 14 109
20 22 43
8 3 352
14 21 837
14 10 4
12 31 532
22 28 130
22 3 197
11 14 583
33 23 612
14 33 621
2 19 27
2 28 957
22 18 458
34 17
29 23 568
28 17 46
4 14 469
22 12 43
6 31 98
13 11 239
19 8 799
3 13 91
7 25 116
2 4 287
25 11 844
7 12 931
28 15 839
5 4 943
10 14 630
28 2 310
1 33 920
66 93
44 22 96
54 14 14
38 26 235
35 4 334
3 26 168
44 47 162
15 53 890
61 22 405
11 19 159
12 55 712
33 61 736
45 7 185
2 45 303
5 3 263
28 4 845
6 2 264
58 10 627
12 64 619
30 14 611
17 43 212
11 20 752
18 39 892
60 45 375
62 20 343
65 30 972
64 41 194
8 30 628
5 31 585
16 24 541
58 28 546
12 41 430
50 20 670
26 42 278
45 64 491
6 25 22
47 10 350
8 65 709
37 45 606
60 36 828
19 54 843
59 21 54
11 64 888
52 54 838
49 39 278
5 17 782
15 57 194
11 29 779
55 6 542
22 53 413
9 50 693
27 38 282
22 35 625
9 13 921
47 14 926
61 59 292
50 42 374
10 7 364
16 42 891
2 48 228
51 46 227
20 63 123
52 6 348
62 23 259
7 25 136
66 7 158
41 62 349
46 61 57
19 4 682
66 1 829
46 19 15
42 44 393
45 27 17
1 33 154
23 46 643
29 40 759
23 24 976
17 57 797
21 33 70
21 25 649
38 18 635
15 59 31
39 52 191
5 31 739
49 1 594
20 45 682
43 21 676
33 35 258
65 26 173
23 35 622
38 43 212
31 29 480
14 53 239
42 56 838
26 88
3 4 360
16 13 482
1 25 579
18 25 853
6 20 196
10 8 879
11 6 886
18 18 925
13 9 846
18 7 505
24 16 448
10 6 73
9 2 374
7 10 623
2 13 355
10 10 89
15 26 35
6 15 461
16 5 506
24 16 388
16 23 875
21 7 898
23 5 232
8 4 775
23 23 601
6 21 720
5 4 898
22 25 678
26 13 152
18 13 598
16 5 323
22 19 377
2 19 932
8 1 876
4 18 132
1 10 206
6 11 356
7 2 779
19 24 397
6 13 437
12 24 714
4 24 55
25 21 155
25 15 767
16 19 204
1 19 442
11 1 639
12 13 139
11 22 405
24 4 322
23 6 277
23 22 145
17 8 514
7 24 616
2 22 916
22 24 632
22 26 867
8 12 515
3 3 256
9 13 931
14 6 137
9 10 199
19 20 182
18 25 18
13 7 273
11 5 79
12 3 23
23 11 150
26 9 860
14 18 617
20 1 170
3 5 924
22 7 623
23 25 422
3 26 88
7 3 206
9 2 218
22 23 763
4 1 358
23 7 721
24 24 243
4 1 821
11 13 669
11 19 303
10 18 28
15 4 760
18 1 130
16 12 75
32 4
2 8 288
2 20 245
3 15 62
9 25 803
7 156
4 3 625
5 5 653
2 5 412
4 4 232
5 2 999
4 3 800
4 2 293
1 5 136
7 2 432
1 7 485
1 2 160
5 2 962
2 7 425
4 6 97
5 4 308
5 7 158
4 4 988
1 7 751
1 6 577
7 6 896
7 6 761
6 7 957
5 5 738
4 2 562
5 2 108
2 5 126
6 4 485
3 4 13
6 5 543
5 3 37
1 1 819
7 5 510
4 1 144
3 1 826
2 5 94
6 3 19
7 6 21
4 3 773
6 7 719
2 1 984
2 1 741
6 5 461
4 2 486
5 7 550
7 3 440
2 2 154
5 7 853
7 3 591
5 6 431
5 1 640
3 7 802
7 4 367
6 5 294
6 2 8
6 1 73
5 2 597
4 6 86
4 2 335
3 5 739
3 1 839
1 3 673
2 6 59
7 4 889
1 6 304
2 2 442
1 3 467
6 5 16
5 2 494
2 4 980
2 3 574
2 2 570
6 3 778
2 3 968
5 7 316
5 6 63
7 4 958
2 5 153
1 2 884
5 7 48
5 1 771
5 4 378
7 3 674
1 5 404
7 5 482
3 5 989
5 4 615
2 1 339
3 3 247
7 2 674
7 1 739
1 7 280
3 7 970
1 5 556
3 2 619
7 4 462
1 1 218
1 2 663
1 4 503
7 5 923
1 7 591
5 7 703
4 4 897
6 6 571
7 7 72
2 6 718
7 7 260
2 3 967
5 7 370
7 4 664
7 7 586
6 3 598
1 5 768
6 7 769
3 2 4
1 4 338
5 5 757
5 6 875
4 3 722
7 2 235
7 5 87
7 7 399
2 3 69
6 3 137
5 7 469
1 7 373
3 1 694
1 2 647
1 3 897
7 7 634
3 2 473
2 2 694
2 6 999
4 3 285
4 3 122
1 4 274
2 5 146
3 1 310
3 7 420
1 5 848
2 7 945
1 6 989
7 4 267
2 2 549
3 4 291
6 5 810
1 2 132
6 4 14
6 5 21
1 4 184
5 2 429
3 5 533
4 4 205
4 5 895
7 3 47
2 1 133
1 7 906
82 41
62 67 18
56 76 748
38 24 324
21 11 535
54 72 425
49 35 273
75 70 359
36 28 46
70 80 234
50 17 863
36 80 887
29 78 240
52 24 469
64 22 818
55 82 699
7 15 785
77 73 455
24 53 172
24 39 23
40 38 161
39 69 356
34 78 787
57 63 244
80 4 386
79 49 279
13 67 784
4 51 551
56 32 620
12 47 227
51 50 152
38 22 795
35 31 172
15 68 723
21 76 770
69 67 538
54 30 144
24 82 860
55 47 735
20 38 816
71 52 336
11 25 850
88 135
34 38 192
10 88 419
76 80 30
20 51 922
64 4 285
74 31 891
52 38 116
70 69 568
18 43 863
81 7 641
30 46 282
5 78 335
85 75 158
47 7 209
50 5 404
56 3 148
69 20 318
49 17 304
68 31 316
74 87 177
7 15 279
84 65 132
71 36 596
53 58 174
33 75 306
36 3 628
55 45 189
47 74 695
77 60 700
52 39 668
66 10 189
42 74 768
53 54 510
86 7 138
72 5 574
51 5 100
7 60 300
56 7 980
27 67 705
41 42 340
26 43 215
11 74 302
40 76 938
22 61 658
3 74 293
7 7 626
66 64 115
72 63 460
51 20 273
68 30 561
86 3 810
71 42 989
35 10 920
71 30 199
56 24 0
38 2 321
13 5 479
75 15 973
7 55 878
12 34 893
15 28 685
32 48 826
41 77 80
46 10 961
46 53 294
47 9 655
27 60 834
17 63 439
72 50 523
81 63 98
20 32 505
67 86 649
32 10 141
41 57 300
69 85 784
78 57 884
49 66 917
87 63 998
49 47 278
87 77 721
6 31 196
3 86 895
77 61 115
45 51 848
41 87 600
9 56 64
50 71 251
25 25 330
47 59 273
36 52 649
66 37 659
39 41 57
75 88 982
38 78 200
36 85 55
4 48 150
50 88 212
74 88 382
20 62 481
71 61 341
83 58 440
36 60 593
11 41 519
65 74 671
61 63 37
84 69 92
83 59 720
58 10 836
7 74 126
67 8 562
36 41 861
72 27 911
24 27 295
74 38 129
48 62 952
4 10 361
62 48 422
72 24 75
57 74 31
40 31 874
56 34 940
82 8 270
84 17 231
10 37 494
71 32 259
80 40 582
16 66 682
39 63 392
24 4 474
30 64 99
40 79 919
47 41 752
64 74 501
76 18 375
83 12 736
24 88
9 19 253
19 2 493
20 9 498
13 16 534
13 14 444
12 13 674
4 11 483
16 2 523
4 21 747
15 16 230
10 9 986
3 20 423
3 13 942
11 10 935
24 22 716
4 16 416
14 2 557
8 13 199
4 17 216
19 9 969
20 20 31
15 16 283
20 7 939
5 9 145
2 23 726
9 18 433
10 17 429
14 19 646
6 4 321
6 16 435
18 11 803
9 15 59
7 22 7
15 23 143
6 10 382
15 20 167
7 1 172
1 11 570
4 5 883
12 18 237
22 1 866
13 4 752
2 13 699
16 9 960
1 1 847
12 18 77
4 11 67
6 13 62
2 20 263
19 24 574
20 10 274
23 13 85
3 17 980
3 19 205
3 11 979
12 1 644
22 5 705
10 7 900
21 18 254
20 1 91
6 10 844
18 1 696
2 12 326
20 24 813
23 3 298
23 6 474
19 4 888
1 13 711
11 20 203
3 12 247
12 14 461
5 12 328
16 23 981
16 5 118
18 12 8
16 14 880
19 10 809
24 20 172
19 14 414
22 21 105
3 23 511
14 22 595
5 6 753
9 16 654
12 14 883
1 17 36
3 3 831
22 14 279
85 159
15 31 847
70 17 76
43 4 457
74 54 856
46 82 235
39 64 422
53 77 618
41 77 384
27 44 959
31 41 705
61 56 246
34 37 201
80 32 358
48 42 800
44 50 303
22 3 151
55 11 571
3 65 337
46 21 315
43 74 881
14 74 417
7 4 731
38 45 672
36 43 448
42 71 849
45 60 807
55 3 593
76 39 184
11 31 980
84 50 752
73 56 367
33 79 361
34 8 811
33 59 863
60 71 755
35 41 29
79 32 801
32 35 686
63 40 68
69 47 907
81 12 286
31 32 762
39 16 535
54 80 34
40 51 679
80 21 842
69 78 294
60 60 988
56 33 950
59 57 804
71 80 431
59 47 629
75 3 437
26 77 218
76 55 801
53 8 651
45 36 956
62 58 308
51 26 893
22 13 759
17 25 969
20 32 268
23 69 18
56 17 721
68 60 928
75 15 393
67 48 147
39 65 990
21 12 988
33 57 829
14 33 110
45 78 808
71 11 992
44 19 578
18 50 601
74 72 738
36 61 521
57 51 244
26 18 277
82 34 877
71 72 538
63 40 690
73 28 653
48 79 172
13 16 538
84 20 169
59 12 97
66 71 968
83 83 89
32 72 354
60 9 211
57 2 9
84 39 636
77 18 179
50 40 672
69 36 420
38 20 437
23 81 250
20 29 539
48 2 912
57 13 576
15 9 642
53 24 918
27 69 775
23 76 101
15 10 878
34 69 841
71 58 512
15 27 516
58 79 439
28 76 849
78 48 972
17 75 498
85 58 771
75 74 962
41 54 298
24 59 330
81 17 774
64 81 357
15 37 99
5 82 425
52 13 854
84 43 84
13 82 444
1 62 111
54 21 448
27 36 874
85 84 205
81 32 693
74 80 876
70 14 354
82 18 704
39 56 568
77 26 243
53 36 124
30 35 2
65 31 135
20 8 363
51 21 890
2 13 920
15 61 202
74 72 276
45 6 112
27 23 899
19 9 715
53 80 212
41 76 379
48 13 545
25 77 173
80 8 621
55 55 369
41 43 460
3 27 129
67 6 150
75 19 968
69 83 1
59 6 82
29 77 392
62 40 827
51 2
17 50 81
45 37 107
36 141
35 24 745
14 17 585
27 13 552
12 14 244
20 9 326
29 2 408
1 28 234
20 22 622
8 18 265
15 18 900
18 1 275
14 33 711
27 11 528
20 16 791
28 27 876
9 28 437
17 13 730
2 25 660
20 36 360
1 6 859
17 27 457
13 27 260
4 4 340
35 23 415
26 33 794
33 7 545
10 8 590
14 10 25
13 28 949
34 16 824
24 35 267
14 15 23
33 8 679
35 8 784
12 6 963
18 32 161
25 11 859
15 21 597
6 17 999
1 12 709
35 7 627
29 15 718
1 35 3
24 2 80
29 3 360
5 10 97
31 13 420
15 21 367
32 26 670
7 3 998
30 13 209
8 10 451
22 1 985
23 25 839
25 27 739
14 24 168
26 34 53
10 16 603
15 9 533
33 6 791
9 20 580
35 33 168
35 18 889
3 3 490
29 11 375
32 27 888
29 12 187
25 26 825
13 19 394
18 23 586
2 14 106
14 33 274
31 4 186
33 31 465
23 25 263
13 7 248
4 18 519
10 19 874
8 26 681
31 11 610
24 28 349
20 34 416
23 2 643
34 21 704
22 6 56
8 35 820
25 4 852
24 18 207
13 19 798
3 13 846
10 24 142
24 36 648
25 5 531
25 4 679
10 15 583
25 12 999
28 1 122
25 30 523
24 32 23
36 6 18
23 25 93
2 32 44
22 22 837
5 30 656
19 20 656
10 10 411
10 24 549
4 26 898
15 11 22
20 8 293
25 7 10
20 31 833
21 7 866
14 23 752
13 27 575
23 21 701
26 19 639
15 9 621
5 3 474
12 4 376
34 36 171
28 18 3
14 17 901
36 17 703
7 21 470
7 23 93
26 14 263
34 14 101
36 18 821
19 16 444
18 13 990
15 35 240
31 19 932
27 8 899
11 6 179
13 16 738
26 13 365
3 14 611
36 30 62
31 29 742
24 4 942
73 13
39 32 856
53 73 125
49 49 789
39 69 612
29 19 529
54 55 399
66 13 370
6 55 853
19 42 780
22 11 76
37 30 613
21 30 772
69 54 829
70 189
19 34 782
68 34 739
33 26 741
32 41 370
12 21 685
39 24 190
21 22 872
16 69 98
59 58 141
58 69 973
33 9 105
8 42 768
34 4 518
16 38 949
36 37 923
1 11 365
35 69 885
45 56 16
32 36 920
42 34 31
51 69 898
34 65 181
37 59 291
4 14 177
52 25 302
4 48 729
3 51 294
70 16 816
35 54 328
68 34 926
66 1 202
3 12 560
61 30 117
16 24 615
41 32 112
30 18 295
22 16 662
37 48 466
32 54 115
65 33 751
7 53 725
18 66 453
47 29 392
12 41 60
44 67 787
3 5 113
18 29 476
65 54 68
60 21 216
34 9 910
28 19 489
23 24 852
64 43 869
34 40 522
42 64 988
59 1 259
17 48 756
12 47 80
32 23 429
53 31 129
1 56 106
36 6 253
8 54 819
59 9 231
64 58 796
6 21 696
54 57 845
42 51 595
64 40 793
36 41 174
22 64 870
39 56 294
22 70 901
43 8 390
42 60 894
4 26 507
60 38 345
53 8 263
34 60 640
4 3 71
9 10 469
6 29 630
6 13 477
25 16 498
26 19 286
52 15 138
31 29 385
39 26 400
28 6 956
42 62 170
63 13 865
33 67 453
45 19 571
2 62 35
32 32 78
58 42 495
17 56 362
54 2 834
2 69 193
63 42 925
5 18 511
13 14 893
31 16 673
34 23 442
65 66 280
37 7 80
22 68 39
23 20 193
34 10 114
17 39 822
46 51 77
59 67 660
17 33 889
39 67 240
47 32 903
65 40 163
62 24 540
24 35 727
45 42 125
26 38 690
6 50 662
15 66 525
47 24 422
56 24 305
17 46 209
57 4 211
22 10 807
68 37 47
40 29 77
19 66 780
69 49 77
6 7 171
42 36 955
65 10 790
52 35 117
67 36 908
6 43 551
43 42 157
13 5 540
9 1 502
69 34 245
6 3 157
53 67 898
62 38 43
39 64 835
4 61 556
47 43 678
30 47 432
34 48 234
47 30 209
10 42 357
24 53 410
21 69 511
70 68 773
6 61 881
66 36 44
38 8 165
14 67 48
3 28 742
44 25 703
16 19 21
10 35 155
20 56 274
17 59 644
7 7 124
43 52 451
62 54 222
58 32 369
27 39 670
51 33 733
11 4 61
45 54 900
30 69 405
30 47 165
49 24 223
42 6 794
25 65 52
56 21 748
36 3 931
68 70 906
1 40 502
66 37 146
7 43 870
53 10 561
18 63 995
35 52 740
29 26 151
61 60 84
6 12 587
38 76
1 7 326
24 36 204
3 3 982
29 9 854
7 13 891
7 12 841
14 38 274
27 12 761
17 3 996
14 10 851
21 6 611
34 7 564
36 8 663
23 37 321
13 31 230
3 21 825
2 2 157
30 9 642
32 27 209
3 38 54
8 7 369
30 31 982
37 24 275
35 35 63
5 37 835
25 23 186
4 15 19
28 15 749
16 4 72
31 9 105
38 27 356
8 28 841
10 17 763
6 26 794
20 13 477
4 13 393
35 30 692
11 11 718
30 21 853
38 24 470
27 29 422
32 35 699
10 32 864
14 11 270
26 18 930
16 7 761
8 20 900
18 37 573
1 5 732
24 4 277
31 12 952
27 19 125
21 12 470
9 13 261
5 20 251
11 25 965
9 11 899
7 9 452
11 17 993
14 33 974
4 33 119
22 36 856
11 17 332
24 23 2
21 4 350
23 10 541
33 10 968
19 17 12
14 20 393
8 22 652
2 26 569
38 22 255
32 1 409
32 15 276
35 38 816
22 21 266
13 81
6 13 835
12 7 191
1 10 922
11 2 936
8 3 448
2 7 817
7 4 517
4 12 910
10 11 343
12 2 316
1 5 948
9 4 592
5 3 629
6 5 7
8 1 956
3 12 157
6 11 459
6 13 36
3 5 119
7 12 469
11 11 207
3 5 482
8 12 893
1 7 366
1 1 983
12 4 446
9 9 384
9 6 261
2 11 958
13 12 11
13 13 43
4 2 888
5 13 734
11 3 886
13 13 588
3 6 978
13 2 563
8 4 168
5 13 776
3 13 37
4 7 959
7 11 869
7 6 288
11 9 606
10 1 759
4 6 773
6 10 114
11 12 244
12 8 888
11 6 164
4 6 233
3 4 301
11 8 542
8 3 537
8 10 963
2 5 181
12 5 329
10 2 100
4 8 827
12 5 84
6 4 576
9 8 724
6 6 417
10 10 388
9 13 904
13 1 170
6 6 236
7 4 665
1 13 934
7 6 199
10 12 498
7 11 789
12 12 630
11 12 0
12 6 816
2 9 904
7 13 346
12 3 950
13 3 956
6 9 634
6 13 146
28 124
17 13 654
3 10 823
28 17 379
15 4 529
19 20 849
22 1 786
12 19 697
14 19 922
19 7 346
22 25 958
6 15 668
15 26 388
16 26 418
19 28 955
22 1 393
22 24 178
24 12 913
26 1 293
16 18 306
25 4 847
11 26 805
20 8 892
1 4 39
13 28 458
13 23 768
20 19 320
3 9 528
3 6 584
5 4 981
8 17 350
17 10 906
8 5 991
11 14 428
11 10 596
5 8 95
7 11 394
27 7 658
4 10 273
20 23 472
8 24 670
1 4 754
17 23 152
2 17 873
11 23 22
2 14 247
24 16 249
2 22 207
24 1 413
2 11 471
9 9 686
13 26 285
7 15 73
23 11 944
1 18 623
14 6 261
14 11 934
7 6 342
7 11 12
2 20 530
22 20 875
4 23 85
2 27 760
13 19 507
2 24 135
19 12 241
1 14 919
18 11 944
13 9 283
4 27 521
8 18 198
2 17 294
12 1 253
14 18 227
10 26 468
5 22 999
18 15 65
28 22 610
21 18 837
3 5 231
20 5 193
20 11 788
20 19 990
22 13 183
19 3 691
24 22 756
10 4 710
15 26 104
17 21 354
21 1 780
10 24 983
20 14 456
22 1 356
19 28 444
21 13 225
15 18 145
2 28 516
11 12 875
3 23 237
15 10 505
10 27 579
7 19 658
20 18 416
19 5 417
15 13 958
5 23 124
16 28 297
27 27 851
21 12 84
2 13 526
12 18 405
2 5 917
4 6 846
8 17 254
5 2 945
27 20 987
11 23 828
9 12 487
20 26 758
4 11 686
5 11 48
21 4 830
27 15 173
15 18 818
1 23 826
24 188
10 2 507
17 20 270
2 4 265
16 3 655
20 2 950
23 11 650
15 3 576
15 1 729
10 16 135
1 8 486
2 23 203
14 20 58
17 13 400
12 19 190
13 7 355
23 22 879
18 3 231
10 23 138
1 16 172
24 19 412
22 16 453
18 21 455
22 11 137
16 2 793
14 8 453
3 10 467
22 1 628
12 7 39
4 19 634
22 16 110
13 5 888
10 20 403
12 15 997
13 3 243
12 18 178
13 22 751
14 16 922
12 3 646
7 23 32
22 12 837
19 1 925
14 3 498
20 14 307
23 22 752
8 21 402
5 1 614
20 24 574
14 20 205
5 4 336
16 14 828
8 14 401
2 11 200
15 24 370
12 1 48
24 5 26
17 21 137
16 2 850
12 11 789
7 16 996
12 11 793
2 4 981
12 14 448
3 6 596
3 17 803
24 18 619
20 2 605
21 15 510
8 8 946
15 22 558
2 8 379
21 1 937
2 2 153
7 21 218
15 6 128
24 18 947
2 6 144
8 18 335
15 14 404
4 4 245
11 9 194
12 17 460
5 2 443
17 22 654
14 12 151
8 21 295
13 5 180
23 1 565
4 17 369
7 8 1000
7 5 834
23 4 352
24 6 537
13 18 526
1 5 914
13 22 194
10 14 676
10 24 272
2 17 565
9 16 118
5 19 872
8 9 512
14 17 358
23 6 871
19 12 650
16 23 823
22 9 25
13 7 403
5 4 671
12 19 852
7 17 571
7 14 23
23 9 358
5 3 19
8 2 351
22 17 813
6 21 391
12 1 646
7 15 452
2 21 869
10 4 895
23 15 745
7 9 80
2 1 820
3 15 797
12 23 926
8 15 471
8 4 418
14 21 38
11 18 970
6 19 948
20 1 915
20 6 3
20 9 951
2 8 938
17 6 995
7 1 943
3 17 808
23 12 373
9 14 621
3 9 782
19 14 427
24 9 961
8 10 49
15 13 405
20 10 757
20 18 538
4 1 830
16 7 657
21 3 781
6 1 70
11 12 801
19 10 26
4 20 517
8 9 93
9 7 240
18 6 194
18 3 805
17 18 801
19 7 600
20 21 481
23 12 773
1 14 389
20 16 643
20 9 866
18 24 303
23 19 642
17 18 822
10 20 342
17 13 575
13 18 521
16 21 963
22 9 16
13 8 642
13 2 198
12 3 161
23 13 597
16 17 735
11 14 402
15 19 948
8 10 150
20 21 462
5 14 683
4 7 840
5 11 139
7 10 55
20 18 448
4 1 891
17 17 879
AC output:

Code: Select all

Case #1 : 13092
Case #2 : No way
Case #3 : 3088
Case #4 : No way
Case #5 : No way
Case #6 : 3960
Case #7 : No way
Case #8 : 136
Case #9 : No way
Case #10 : No way
Case #11 : 3361
Case #12 : No way
Case #13 : No way
Case #14 : 5977
Case #15 : No way
Case #16 : No way
Case #17 : 12337
Case #18 : 1336
Case #19 : 5028
Case #20 : 1938

Re: 10462 - Is There A Second Way Left?

Posted: Mon Oct 06, 2014 9:49 pm
by brianfry713
Input:

Code: Select all

1
2 2
1 2 0
1 2 0
AC output:

Code: Select all

Case #1 : 0

Re: 10462 - Is There A Second Way Left?

Posted: Sat Oct 25, 2014 11:42 am
by saeedcsedu
why wrong answer:
my code:

Code: Select all

#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
int flag=0,flag1=0;
int par[105],v,cost=0,t=0;
struct data
{
    int node1,node2;
    int weight;
     bool operator < (const data &p) const
    {
        return (weight>p.weight);
    }
};
priority_queue <data> q,q_a;
priority_queue <data> q1;
int find(int r)
{
    if(par[r]==r)  return r;
    else
        return find(par[r]);
}
void mst()
{   int j=0,a,b;
    for(int i=1;i<=v;i++) par[i]=i;
    cost=0;
    while(!q.empty())
    {
        data s;
        s=q.top();
        q.pop();
        a=find(s.node1);
        b=find(s.node2);
        if(a!=b)
        {
            par[a]=b;
            j++;
            cost+=s.weight;
            q1.push(s);
        }
        if(j==v-1) break;
    }
}
void mst1(data s1)
{   int j=0,a,b;
    for(int i=1;i<=v;i++) par[i]=i;
    cost=0;
    while(!q.empty())
    {
        data s;
        s=q.top();
        q.pop();
        if(s1.node1==s.node1&&s1.node2==s.node2&&s1.weight==s.weight) continue;
        a=find(s.node1);
        b=find(s.node2);
        if(a!=b)
        {
            par[a]=b;
            j++;
            cost+=s.weight;
        }
        if(j==v-1) break;
    }
    return;
}
int main()
{

    int e,i,j,a,b,wei,c1,c2,te,k;
    cin>>te;
    for(k=1;k<=te;k++)
    {
        cin>>v>>e;
        while(!q.empty()) q.pop();
        while(!q_a.empty()) q_a.pop();
        while(!q1.empty()) q1.pop();
        for(i=0;i<e;i++)
        {
            cin>>a>>b>>wei;
            data s;
            s.node1=a;
            s.node2=b;
            s.weight=wei;
            q.push(s);
        }
        q_a=q;
        mst();
        j=0;
        for(i=1;i<=v;i++) if(par[i]==i) j++;
        if(j>1) cout<<"Case #"<<k<<" : No way"<<endl;
        else if(v>e) cout<<"Case #"<<k<<" : No second way"<<endl;
        else
        {
            c1=cost;
            c2=10000000;
            while(!q1.empty())
            {
                data s=q1.top();
                q1.pop();
                while(!q.empty()) q.pop();
                q=q_a;
                int cnt=0;
                mst1(s);
                for(i=1;i<=v;i++) if(par[i]==i) cnt++;
                if(cnt>1) continue;
                if(c2>cost) c2=cost;
            }
                if(c2==10000000) c2=c1;
                cout<<"Case #"<<k<<" : "<<c2<<endl;
        }
    }
    return 0;
}

Re: 10462 - Is There A Second Way Left?

Posted: Wed Oct 29, 2014 10:56 pm
by brianfry713
Input:

Code: Select all

1
1 2
1 1 1
1 1 2
AC output:

Code: Select all

Case #1 : No second way

Re: 10462 - Is There A Second Way Left?

Posted: Sun Jan 08, 2017 1:05 pm
by ainan.ahmed
Can anyone tell me why i am getting WA?? :(
Tried all the testcase given in this forum & udebug..they all gave correct ans.
my code: http://ideone.com/m5lFmo