is absolutly right. It's the main thing. Euler path.Ryan Pai

may be ur problem in dijkstra or BMF. check this.rafi7

**Moderator:** Board moderators

I solved this problem. I use Floyed and dijkstra. In Floyed it got more time but in dijkstra it take 0.000 sec.

is absolutly right. It's the main thing. Euler path.Ryan Pai

may be ur problem in dijkstra or BMF. check this.rafi7

I hate three things one- Wrong Answer,TL and the problem which statement is not clear.

I would like to clarify whether it is possible to have the following input for this qn:

computer

car

collar

deadend

Here 2 intersections are linked by 3 streets. How would this graph be represented using an adjacency matrix or adjacency list?

My code worked with the sample input but failed the above test case.

computer

car

collar

deadend

Here 2 intersections are linked by 3 streets. How would this graph be represented using an adjacency matrix or adjacency list?

My code worked with the sample input but failed the above test case.

I have checked through my code many times, submitted to OJ, but the OJ keep on replying WA. My code works with the given sample input, and will terminate at EOF(end of file). I find no bug in my code. I am using Djikstra's shortest path algorithm. I am using the integer value 1000000 to represent "infinity" in the adjacency matrix I used to represent the graph. I need only a 2D array of size 26 by 26 maximum since there are a maximum of 26 possible intersections ('a' to 'z' lowercase). Could those who got AC provide some input and output for which my program will fail?

Here is my WA code for problem 117. Any help will be greatly appreciated.

[c]

Resolved.

[/c]

For problem 139, I also get WA, but I find no bug. Here is my WA code for problem 139. My code can handle locality names with spaces such as "Los Angeles" and works with all the input in this forum. Where did I go wrong?

[c]

Resolved.

[/c]

Here is my WA code for problem 117. Any help will be greatly appreciated.

[c]

Resolved.

[/c]

For problem 139, I also get WA, but I find no bug. Here is my WA code for problem 139. My code can handle locality names with spaces such as "Los Angeles" and works with all the input in this forum. Where did I go wrong?

[c]

Resolved.

[/c]

Last edited by chunyi81 on Sun Jul 25, 2004 4:03 pm, edited 4 times in total.

Can someone help me with problem 139 please? My code works with all the input in this board, but the judge keep on replying WA to my code. Where is the bug?

I having trouble solving this problem.

This is my algorithm:

I read edges and add sum them up.

I keep track of how many edges do go from each vertex

If there are two odd degree vertexes, i find the shorthest path from the 2

verticies.

I get WA

This is my code:

[cpp]

#include <iostream>

#include <string>

#include <vector>

#include <climits>

using namespace std;

struct edge

{

int x,y,w;

edge( int a, int b, int c ) { x = a; y = b; w = c; }

};

vector < edge > e;

vector < int > dist;

int slova[300] = { 0 };

int bellman_ford( int start, int end, int n )

{

dist.resize( (int)'a' + 31 );

for( int i = 0; i < dist.size(); ++i ) dist* = 9999999;*

dist[start] = 0;

for( int i = 0; i < n; ++i )

for( int j = 0; j < e.size(); ++j )

dist[e[j].y] <?= dist[e[j].x] + e[j].w;

return dist[end];

}

int main()

{

while( 1 )

{

int s = 0;

vector < int > odd;

string t;

cin >> t;

if( t == "" ) break;

while( t != "deadend" )

{

int a = t[0];

int b = t[t.size()-1];

int c = t.size();

e.push_back( edge( a, b, c ) );

s += c;

++slova[a]; ++slova**;**

if( slova[a] % 2 != 0 && slova[a] != 1 ) odd.push_back( a );

if( slova** % 2 != 0 && slova**** != 1 ) odd.push_back( b );**

cin >> t;

}

//How many verticies do we have

int n = 0;

for( int i = 0; i < 300; ++i )

if( slova* > 0 ) ++n;*

if( odd.size() == 0) cout << s << endl;

else cout << s + bellman_ford( odd[0], odd[1], n ) << endl;

//Cleaning

e.clear();

dist.clear();

for( int i = 0; i < 300; ++i ) slova* = 0; *

}

return 0;

}[/cpp]

This is my algorithm:

I read edges and add sum them up.

I keep track of how many edges do go from each vertex

If there are two odd degree vertexes, i find the shorthest path from the 2

verticies.

I get WA

This is my code:

[cpp]

#include <iostream>

#include <string>

#include <vector>

#include <climits>

using namespace std;

struct edge

{

int x,y,w;

edge( int a, int b, int c ) { x = a; y = b; w = c; }

};

vector < edge > e;

vector < int > dist;

int slova[300] = { 0 };

int bellman_ford( int start, int end, int n )

{

dist.resize( (int)'a' + 31 );

for( int i = 0; i < dist.size(); ++i ) dist

dist[start] = 0;

for( int i = 0; i < n; ++i )

for( int j = 0; j < e.size(); ++j )

dist[e[j].y] <?= dist[e[j].x] + e[j].w;

return dist[end];

}

int main()

{

while( 1 )

{

int s = 0;

vector < int > odd;

string t;

cin >> t;

if( t == "" ) break;

while( t != "deadend" )

{

int a = t[0];

int b = t[t.size()-1];

int c = t.size();

e.push_back( edge( a, b, c ) );

s += c;

++slova[a]; ++slova

if( slova[a] % 2 != 0 && slova[a] != 1 ) odd.push_back( a );

if( slova

cin >> t;

}

//How many verticies do we have

int n = 0;

for( int i = 0; i < 300; ++i )

if( slova

if( odd.size() == 0) cout << s << endl;

else cout << s + bellman_ford( odd[0], odd[1], n ) << endl;

//Cleaning

e.clear();

dist.clear();

for( int i = 0; i < 300; ++i ) slova

}

return 0;

}[/cpp]

I'm gettin 117 WA.Give some tests please.

Thanks.

Thanks.

someone who like to solve informatic problems.

http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Ok Sohel.

My algo.

Vertexes of graph are letters 'a'..'z'.Let K be number of vertexes wich have odd nodes.

if k=0 then answer=sum length(of all words).

k can't be 1!

if k=2 then answer=sum length(of all words)+shortest path from one odd vertex to another.

Eduard

My algo.

Vertexes of graph are letters 'a'..'z'.Let K be number of vertexes wich have odd nodes.

if k=0 then answer=sum length(of all words).

k can't be 1!

if k=2 then answer=sum length(of all words)+shortest path from one odd vertex to another.

Eduard

someone who like to solve informatic problems.

http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

I find my little mistake and got AC.

someone who like to solve informatic problems.

http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Code: Select all

```
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define FOR(a,b) for(int a=0;a<b;a++)
#define MAXI (50)
int mat[MAXI][MAXI];
int t[MAXI];
void clear() {
FOR(i,MAXI) FOR(j,MAXI) mat[i][j]=2<<10;
FOR(i,MAXI) t[i]=0;
}
void floyd() {
FOR(i,MAXI) FOR(j,MAXI) if(i!=j) FOR(k,MAXI) if(i!=k && j!=k)
mat[j][k] = min(mat[j][i]+mat[i][k],mat[j][k]);
}
int main() {
char lin[10001];
while(true) {
clear();
int tot = 0;
while(true) {
// reads a line, if it should stop, stop
if(!(gets(lin))) return 0;
if(strlen(lin)==0) continue;
// if deadend --> next
if(strcmp(lin,"deadend")==0) break;
// connects them
int d = lin[0]-'a';
int p = lin[strlen(lin)-1]-'a';
t[d]++; t[p]++;
tot += strlen(lin);
mat[d][p] = min(mat[d][lin[p]],(int) strlen(lin));
}
floyd();
FOR(i,MAXI) if(t[i]%2) {
for(int j=i+1;j<MAXI;j++) if(t[j]%2) {
cout << (mat[i][j]+tot) << endl;
goto n;
}
}
cout << tot << endl;
n:;
}
}
```

- sahand
- New poster
**Posts:**19**Joined:**Sat Mar 12, 2005 5:56 pm**Location:**Halifax, Nova Scotia, Canada-
**Contact:**

Hi,

This is my code for 117. It works for the sample inputs but I get WA when I submit it. Please help.

This is my code for 117. It works for the sample inputs but I get WA when I submit it. Please help.

Code: Select all

```
Code removed!
```

Last edited by sahand on Fri Apr 22, 2005 3:30 pm, edited 1 time in total.