117 - The Postal Worker Rings Once

[Grinder]

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

Ryan Pai

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

rafi7

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

[chunyi81]

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.

[chunyi81]

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]

[chunyi81]

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?

[chunyi81]

Please help. Thanks.

[chunyi81]

For problem 139, I realised that there is one very tricky input that I have overlooked. For STD codes 00 is a valid STD code, and not a IDD code.

Input
00 123$10
000000
001234 1
#

Correct Output:
001234 123 1234 1 0.10 0.10

Hope this helps others who are still trying to solve the problem.

[sklitzz]

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]

[Eduard]

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

[sohel]

Instead of directly asking for test cases,
why don't you describe your algorithm..
.. in this way everyone will be helpful including you.

[Eduard]

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

[Eduard]

I find my little mistake and got AC.

[ImLazy]

Oh, I was so stupid that I used to think this problem very complicated. But now I see your algorithm which is so good. Thank you.

[technobug]

Hmmm... i tried going with floyd warshal...... the rest is the same. Any ideas?

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]

Hi,
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!

[Sanny]

The graph is undirected.

Regards
Sanny