## 567 - Risk

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

Moderator: Board moderators

fcarlos
New poster
Posts: 5
Joined: Sat Jul 27, 2002 4:16 am

### 567 - Risk

Seemingly, the ouput of my program is correct, but the judge give it, always WA, i would like to know if the error is because
1. My output is not correctly formatted, or
2. My algorithm is not correct.

Thanks in advance

[cpp]
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
using namespace std;
const int MAX_COUNTRIES = 20;
const int NLINES = 19;
const int INFINITY = 32767;

class WFalgorithm {
public:
void initialize( int );
void shortestAllPath( int );
int getMinimumCost( int , int );
void begin( void );
private:
// length of shortest path between i and j
int d[ MAX_COUNTRIES ][ MAX_COUNTRIES ];
// length of direct edge between i and j
int w[ MAX_COUNTRIES][ MAX_COUNTRIES ];
vector<string> v;
};

int main( void ) {
WFalgorithm wf ;
wf.begin();
}

void WFalgorithm::begin( void ) {

int borders;
int country;
int N;
int testCase = 1;

while ( !cin.eof() ) {

// initialize gameboard
for ( int i = 0; i < MAX_COUNTRIES ; i++ ) {
for ( int j = 0; j < MAX_COUNTRIES; j++ ) {
w[ i ][ j ] = INFINITY;
}
}

for ( int i = 1; i <= NLINES; i++ ) {
cin >> borders;
if ( borders == 0 ) continue;
for ( int j = 1; j <= borders; j++ ) {
cin >> country;
w[ i -1 ][ country - 1 ] = 1;
w[ country - 1 ][ i - 1 ] = 1;
}
}

cin >> N;
initialize( MAX_COUNTRIES );
shortestAllPath( MAX_COUNTRIES );
string header("Test Set #" );
cout << header << testCase << endl;
int origin, destin;
for ( int i = 1; i <= N; i++ ) {
cin >> origin >> destin;
int result = getMinimumCost( origin , destin );

cout << setw( 2 ) << resetiosflags( ios::right ) << origin ;
cout << setw( 4 ) << resetiosflags( ios::left ) << " to " ;
cout << setw( 2 ) << resetiosflags( ios::right ) << destin ;
cout << ":" ;
cout << resetiosflags( ios::left ) << setw( 2 ) << result << endl;
}
cout << endl;
cin.get();
testCase += 1;
} // outer while

}

void WFalgorithm::initialize( int n ) {
for ( int i = 0; i < n; i++) {
for ( int j = 0; j < n; j++) {
d[j] = w[j];
}
}
}

void WFalgorithm::shortestAllPath( int n ) {
for (int k=0;k<n;k++)
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
if (d[k] + d[k][j] < d[j]) {
d[j] = d[k] + d[k][j];
}
}

int WFalgorithm::getMinimumCost( int i, int j ) {
return d[ i - 1 ][ j - 1 ];
}
[/cpp]
Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
If you not correctly format output, you got PE At first look your program should works .... I use the same algorithm (Floyd) to find shortest paths between coutries ...

Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
fcarlos
New poster
Posts: 5
Joined: Sat Jul 27, 2002 4:16 am

### Input sample

Hello, Domini..
I test the given input, and i am getting the ouput correctly..
could you give some ohter sample input for test it?

Carlos
boatfish
New poster
Posts: 18
Joined: Thu May 08, 2003 11:46 am

### 567

I tested many cases, all are right.
But it keeps on WA.
[cpp]#include<iostream>
using namespace std;

int table;

void fw(){
int i,j,k;
for(k=1;k<=20;k++)
for(i=1;i<=20;i++)
for(j=1;j<=20;j++)
if(table[k]+table[k][j]<table[j])
table[j]=table[k]+table[k][j];
}

int main(){
int i,no,t,case_no=0,j,n,x,y;
while(cin.peek()!=EOF){
case_no++;
for(i=1;i<=20;i++)
for(j=1;j<=20;j++)
if(i==j)
table[j]=0;
else
table[j]=100;
for(i=1;i<=19;i++){
cin>>no;
for(j=1;j<=no;j++){
cin>>t;
table[t]=1;
table[t]=1;
}
}

fw();
cout<<"Test Set #"<<case_no<<endl;
cin>>n;
for(i=1;i<=n;i++){
cin>>x>>y;
cout.width(2);
cout<<x<<" to ";
cout.width(2);
cout<<y<<": "<<table[x][y]<<endl;
}
cout<<endl;
}
return 0;
}[/cpp]
Xeno
New poster
Posts: 4
Joined: Mon Nov 17, 2003 2:01 am
Location: Colorado, USA

### 567 (Risk) - Wrong Answer

[cpp]// http://acm.uva.es/p/v5/567.html

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

const int n = 20;

int main()
{
int set = 0;

while (!cin.eof())
{
set++;
vector<vector<int> > table(n, vector<int>(n, 0));

for (int i = 0; i < n - 1; ++i)
{
int hnn; // higher-numbered neighbors
cin>>hnn;

for (int j = 0; j < hnn; ++j)
{
int neighbor;
cin>>neighbor;
table[neighbor - 1] = 1;
table[neighbor - 1] = 1;
}
}

// Floyd-Warshall the mofo
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
if (table[k] != 0)
for (int j = 0; j < n; ++j)
if (table[k][j] != 0)
if (table[j] == 0 || table[k] + table[k][j] < table[j])
table[j] = table[k] + table[k][j];

cout<<"Test Set #"<<set<<endl;
int pairs;
cin>>pairs;

for (int i = 0; i < pairs; ++i)
{
int from, to;
cin>>from>>to;

cout<<setiosflags(ios::right)<<setw(2)<<from<<" to "<<setw(2)<<to<<": "<<setiosflags(ios::left)<<table[from - 1][to - 1]<<endl;
}

cout<<endl;
}
}[/cpp]

I have no idea why the judge isn't accepting my program. It works for all the example inputs and it even works for another test case that I got from elsewhere on the web (http://www.geocities.com/acmbeganer/p567io.htm). I can only surmise that there is some special input that I must account for, but after thoroughly scanning the problem statement, I can't figure out what it is. Any ideas?
You're in a maze of twisty compiler features, all different.
Xeno
New poster
Posts: 4
Joined: Mon Nov 17, 2003 2:01 am
Location: Colorado, USA
Bumpity. Come on, someone out there must have solved this problem. What's wrong with my code?
You're in a maze of twisty compiler features, all different.
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Your terminating condition doesn't terminate correctly. Let's say, that the last input had a few spaces after. Then, your !cin.eof () would return true, since you're not at the end of file yet, and thus, while continue trying to read the next number.
Xeno
New poster
Posts: 4
Joined: Mon Nov 17, 2003 2:01 am
Location: Colorado, USA
Exactly right, UFP2161. I changed my terminating condition and it worked like a charm. Thanks a lot.

In my defense, the judge gets mad when submissions generate answers with extraneous whitespace, so I don't think it's right that the judge's input files have extra whitespace in them. Gar. You're in a maze of twisty compiler features, all different.
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### Try this.

Greetings!
Try an input with blank lines and/or blank spaces at the end of the data.
Your program won't stop if finds it at the end, and throws wrong output.
I modified it with that, and it's an ACed Ah!, freaking important:
Line 20 of the test set contains a single integer (1 <= N <= 100) indicating the number of country pairs that follow.
Is not true!!!!!
I've spent many WA's to finally find out that the real range is:

(1 <= N <= 300)

Keep posting!
_.
I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:
well, i amm getting OLE for this problem
with this code

Code: Select all

``````cut got ACC...
``````
please help...
thx
Last edited by I LIKE GN on Fri Sep 02, 2005 12:06 pm, edited 1 time in total.
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### Try this.

Greetings!

Try changing char read() for int read() instead.
Read my previous post, the limit in the description is corrupted.
Hope it helps _.
I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

### Re: Try this.

_.B._ wrote:Greetings!

Try changing char read() for int read() instead.
Read my previous post, the limit in the description is corrupted.
Hope it helps many many thanx to UUUUUUUUU
have a nice DAY!!!!
RSS
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### Good.

Glad it helpeld Keep posting! _.
TripShock
New poster
Posts: 14
Joined: Tue Jun 20, 2006 9:33 am

### WA

Can someone please point out why I'm getting WA for this code? It's just a straightforward implementation of Floyd-Warshall...

Code: Select all

``````#include <iostream>
#include <algorithm>
#include <iomanip>

using namespace std;

int main()
{
int Case = 0;
while (true)
{
const int MAX = 20;
const int INF = 999999999;
int D[MAX][MAX] = { 0 };

for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
if (i == j)
D[i][j] = 0;
else
D[i][j] = INF;

for (int i = 0; i < MAX - 1; i++)
{
int Number = 0;
if (!(cin >> Number))
return 0;
for (int j = 0; j < Number; j++)
{
int Country = 0;
cin >> Country;
D[i][Country - 1] = 1;
D[Country - 1][i] = 1;
}
}

for (int k = 0; k < MAX; k++)
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
D[i][j] = min(D[i][j], D[i][k] + D[k][j]);

int Cases = 0;
cin >> Cases;
int From = 0;
int To = 0;

if (Case)
cout << endl;
Case++;
cout << "Test Set #" << Case << endl;
for (int i = 0; i < Cases; i++)
{
cin >> From >> To;
cout << setw(2) << From << " to " << setw(2) << To << ": ";
cout << D[From - 1][To - 1] << endl;
}
}

return 0;
}
``````
Thanks
alamgir kabir
New poster
Posts: 37
Joined: Wed Oct 03, 2007 10:42 am

### WA please help me.

Thanks a lot Sapnil.
I have now ACC.

Code: Select all

``````code removed after ACC.
``````
Thanks.
Last edited by alamgir kabir on Sat Nov 24, 2007 3:45 pm, edited 1 time in total.