### 567 - Risk

Posted:

**Thu Apr 03, 2003 4:22 pm**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

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}

}

}

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]) {*

dd

*[j] = d**[k] + d[k][j];*

}

}

int WFalgorithm::getMinimumCost( int i, int j ) {

return d[ i - 1 ][ j - 1 ];

}

[/cpp]}

}

int WFalgorithm::getMinimumCost( int i, int j ) {

return d[ i - 1 ][ j - 1 ];

}

[/cpp]