567 - Risk

[fcarlos]

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]

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

[fcarlos]

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]

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

int table[21][21];

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]

[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?

[Xeno]

Bumpity. Come on, someone out there must have solved this problem. What's wrong with my code?

[UFP2161]

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]

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.

[_.B._]

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]

well, i amm getting OLE for this problem
with this code

Code: Select all

cut got ACC...

please help...
thx

[_.B._]

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]

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

[_.B._]

Glad it helpeld

Keep posting!

[TripShock]

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]

Thanks a lot Sapnil.
I have now ACC.

Code: Select all

code removed after ACC.

Thanks.