## 1172 - The Bridges of Kolsberg

Moderator: Board moderators

Degiac
New poster
Posts: 2
Joined: Thu Sep 04, 2014 11:41 pm
Location: Salerno, Italy
Contact:

### Re: 1172 - The Bridges of Kolsberg

Has someone got some tricky test cases for this problem? I keep getting WA and I can't realize why. I wrote some test cases myself but I always get the right answer

EDIT: nvm, solved

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

### Re: 1172 - The Bridges of Kolsberg

I added some random input at:
http://www.udebug.com/UVa/1172
Check input and AC output for thousands of problems on uDebug!

New poster
Posts: 17
Joined: Thu Jul 03, 2014 11:13 am

### Re: 1172 - The Bridges of Kolsberg

Hi, Can anybody tell me How to proceed to solve this problem? It looks like matching with some constraints. Please give me some hints?

New poster
Posts: 3
Joined: Thu Jul 09, 2015 5:20 am

### Re: 1172 - The Bridges of Kolsberg

Hey guys,

I solved this problem and only got accepted after considering the constraint: no city could be an endpoint of more than one bridge. Does the problem description imply this constraint ? If anyone got accepted without considering such a constraint, I would appreciate telling me briefly his algorithm to look for my bug, if any.

Thanks

Shafayat
New poster
Posts: 7
Joined: Mon Jan 19, 2015 11:32 am

### Re: 1172 - The Bridges of Kolsberg

Why I'm getting WA?

Code: Select all

``````#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;

struct bridge
{
long long int cost;
char city[1000],os[1000];
}le[1000],ri[1000];     //store inputs. 'le' for first bank and 'ri' for second bank

struct table
{
long long int pos;
long long int co;   // stores the cost
long long int cou;  // count the bridge
}tab[1000][1000];         //table for current maximum cost and minimum number of bridge

/* in this solve function I use algorithm like coin change algorithm.
here, I create a table.
for all bridges in 're', i choose bridge from 'le' and find current maximum cost and minimum number of bridge.*/

void solve(long long int a,long long int b)
{
memset(tab,0,sizeof(tab));
for(long long int i=0;i<a;i++)     //Select bridge from le
{
for(long long int j=0;j<b;j++)   //Select bridge from re
{
if(strcmp(le[i].os,ri[j].os)==0)      // compare OS name
{
if((tab[i][j].co+le[i].cost+ri[j].cost)>tab[i][j+1].co && (tab[i][j].co+le[i].cost+ri[j].cost)>tab[i+1][j].co)  // check if (cost stored in previous diagonal cost from table+ cost of current bridge) is greater than cost stored in upward position and left position of the table
{
tab[i+1][j+1].co=tab[i][j].co+le[i].cost+ri[j].cost;
tab[i+1][j+1].pos=j+1;   // stores the position where I get current maximum
tab[i+1][j+1].cou=tab[i][j].cou+1;   // count the bridge number

}
else if((tab[i][j].co+le[i].cost+ri[j].cost)==tab[i][j+1].co)   // if current cost and cost of upward position in table is same than choose that one which contains minimum number of bridge
{
tab[i+1][j+1].co=tab[i][j].co+le[i].cost+ri[j].cost;
if((tab[i][j].cou+1)<tab[i][j+1].cou)
{
tab[i+1][j+1].pos=j+1;
tab[i+1][j+1].cou=tab[i][j].cou+1;
}
else
{
tab[i+1][j+1].pos=tab[i][j+1].pos;
tab[i+1][j+1].cou=tab[i][j+1].cou;
}

}
else if((tab[i][j].co+le[i].cost+ri[j].cost)==tab[i+1][j].co)  // if current cost and cost of left position in table is same
{
tab[i+1][j+1].co=tab[i][j].co+le[i].cost+ri[j].cost;
if((tab[i][j].cou+1)<tab[i+1][j].cou)
{
tab[i+1][j+1].pos=j+1;
tab[i+1][j+1].cou=tab[i][j].cou+1;
}
else
{
tab[i+1][j+1].pos=tab[i+1][j].pos;
tab[i+1][j+1].cou=tab[i+1][j].cou;
}

}
// conditions after this line works if (cost stored in previous diagonal cost from table+ cost of current bridge) is smaller than upward and left position
else if(tab[i][j+1].co>tab[i+1][j].co)
{
tab[i+1][j+1].co=tab[i][j+1].co;
tab[i+1][j+1].pos=tab[i][j+1].pos;
tab[i+1][j+1].cou=tab[i][j+1].cou;
}
else if(tab[i][j+1].co<tab[i+1][j].co)
{
tab[i+1][j+1].co=tab[i+1][j].co;
tab[i+1][j+1].pos=tab[i+1][j].pos;
tab[i+1][j+1].cou=tab[i+1][j].cou;
}
else
{
if(tab[i][j+1].co==tab[i+1][j].co && tab[i][j+1].cou<tab[i+1][j].cou)
{
tab[i+1][j+1].co=tab[i][j+1].co;
tab[i+1][j+1].pos=tab[i][j+1].pos;
tab[i+1][j+1].cou=tab[i][j+1].cou;
}
else if(tab[i][j+1].co==tab[i+1][j].co && tab[i][j+1].cou>tab[i+1][j].cou)
{
tab[i+1][j+1].co=tab[i+1][j].co;
tab[i+1][j+1].pos=tab[i+1][j].pos;
tab[i+1][j+1].cou=tab[i+1][j].cou;
}
else
{
tab[i+1][j+1].co=tab[i+1][j].co;
tab[i+1][j+1].pos=tab[i+1][j].pos;
tab[i+1][j+1].cou=tab[i+1][j].cou;
}
}
}
else    // if OS name does not matches than I choose from upward and left position
{
if(tab[i][j+1].co>tab[i+1][j].co)
{
tab[i+1][j+1].co=tab[i][j+1].co;
tab[i+1][j+1].pos=tab[i][j+1].pos;
tab[i+1][j+1].cou=tab[i][j+1].cou;
}
else if(tab[i][j+1].co<tab[i+1][j].co)
{
tab[i+1][j+1].co=tab[i+1][j].co;
tab[i+1][j+1].pos=tab[i+1][j].pos;
tab[i+1][j+1].cou=tab[i+1][j].cou;
}
else
{
if(tab[i][j+1].cou<tab[i+1][j].cou)
{
tab[i+1][j+1].co=tab[i][j+1].co;
tab[i+1][j+1].pos=tab[i][j+1].pos;
tab[i+1][j+1].cou=tab[i][j+1].cou;
}
else if(tab[i][j+1].cou>tab[i+1][j].cou)
{
tab[i+1][j+1].co=tab[i+1][j].co;
tab[i+1][j+1].pos=tab[i+1][j].pos;
tab[i+1][j+1].cou=tab[i+1][j].cou;
}
else
{
tab[i+1][j+1].co=tab[i+1][j].co;
tab[i+1][j+1].pos=tab[i+1][j].pos;
tab[i+1][j+1].cou=tab[i+1][j].cou;
}
}
}
}
}

}

int main()
{
long long int a,b,c,d,e,f,g,h;
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
cin>>a;
for(b=1;b<=a;b++)
{
cin>>c;
for(d=0;d<c;d++)
{
cin>>le[d].city>>le[d].os>>le[d].cost;
}
cin>>d;
for(e=0;e<d;e++)
{
cin>>ri[e].city>>ri[e].os>>ri[e].cost;
}
solve(c,d);
for(int i=0;i<=c;i++)
{
for(int j=0;j<=d;j++)
{
printf("%8lld-%lld ",tab[i][j].co,tab[i][j].cou);
}
cout<<endl;
}
printf("%lld %lld\n",tab[c][d].co,tab[c][d].cou);
}
return 0;
}

``````

metaphysis
Experienced poster
Posts: 128
Joined: Wed May 18, 2011 3:04 pm

### Re: 1172 - The Bridges of Kolsberg

Be careful of the boundary condition.

muazuicom22
New poster
Posts: 25
Joined: Tue Sep 11, 2018 10:32 pm
CTY TDL CHUYÊN NHẬN LÀM GIẤY TỜ :

Kính gửi Quý khách hàng , Cty TDL chúng tôi

Nhận làm tất cả các loại giấy tờ liên quan đến BĐS , từ dễ đến khó , khu vực Thành Phố HCM Và Bình Dương.
* Vẽ thiết kế xây dựng, xin giấy phép xây dựng.
* Vẽ hiện trạng đo đạc nhà đất, nhà máy, nhà xưởng.
*Dịch vụ thiết kế Phòng cháy, chữa cháy và Thẩm duyệt.
* Dịch vụ xin chuyển mục đích sử dụng đất.
* Dịch vụ hoàn công nhà xưởng, công trình trên đất.
* Dịch vụ tách thửa sổ đỏ, nhà đất, nhà xưởng, nhà máy.
* Dịch vụ xin cấp mới sổ đỏ, sổ hồng hoặc xin cấp Giấy chứng nhận Quyền sử dụng đất, quyền sở hữu nhà ở và tài sản khác gắn liền với đất.
* Dịch vụ xác định lại ranh giới, thực trạng nhà đất, cấp sổ mới.
* Dịch vụ xem xét lại quy hoạch xây dựng.
* Dịch vụ hợp thức hóa nhà đất.
* Dịch vụ sang tên , đăng bạ sang tên chủ quyền, thừa kế di chúc.

Ai có nhu cầu liên hệ 0938.242.835 c.Hong.
Quý khách Lưu lại khi cần . Trân trọng cảm ơn. Uy Tin_ chinh chuan.
Chúc Anh chị một ngày tốt lành