117 - The Postal Worker Rings Once

[sahand]

Thanks sammy. That was a very funny mistake!
Sahand

[surya ss]

maybe it's out of date or you have it ac, but
I try to give a clue anyway

the clue is : you can't just find the shortest path from just one side,what i mean is :
in this input :
one
two
three

you have 6 path, not 3 path :
detail:
(1) from(o) to (e) length = 3
(2) from(e) to (o) length = 3
(3) from(t) to (o) length = 3
(4) from(o) to (t) length = 3
(5) from(t) to (e) length = 5
(6) from(e) to (t) length = 5

in you code you just have 3 path:
detail
(1) from(o) to (e) length = 3
(2) from(t) to (o) length = 3
(3) from(t) to (e) length = 5

so it got wrong answer
hope it can help

[coldfire]

Hello .. i've tried to solve the problem with both disjktra and roy-floyd but i keep getting WA. Can anyone take a look on my code or give me some test data please ?!

{$S-,R-,Q-,B-}

const hValue = maxlongint div 2;

var i, j, q, nod, nod2: char;
grad: array['a'..'z'] of longint;
d: array['a'..'z', 'a'..'z'] of longint;
s: string;
t: longint;
found: boolean;

procedure read_data;
begin

// assign(input, '117.in'); reset(input);
// assign(output, '117.out'); rewrite(output);

while not eof(input) do begin

readln(s);
t := 0; found := false;
for i := 'a' to 'z' do
for j := 'a' to 'z' do d[i, j] := hValue;

while (s <> 'deadend') do begin

if s <> '' then begin

found := true;
inc(grad[s[1]]); inc(grad[s[length(s)]]);
inc(t, length(s));
d[s[1], s[length(s)]] := length(s);
d[s[length(s)], s[1]] := length(s);

end;

readln(s);

end;

nod := 'A'; nod2 := 'A';
for i := 'a' to 'z' do
if odd(grad) then
if nod = 'A' then nod := i else
if nod2 = 'A' then nod2 := i;

if nod <> 'A' then begin

for q := 'a' to 'z' do
for i := 'a' to 'z' do
for j := 'a' to 'z' do
if d[i, q] + d[q, j] < d[i, j] then d[i, j] := d[i, q] + d[q, j];

t := t + d[nod, nod2];
end;

if found then writeln(t);

end;

// close(input); close(output);

end;

begin

read_data;

end.

[coldfire]

I've solved the problem. Just forgot to fillchar with 0 "grad" (degree) array at each new route

[emotional blind]

I need critical input output for problem,
It is a very simple problem,
But i cant figure out where is my problem..
I am getting WAs,

[emotional blind]

ACCEPTED

[Artikali]

I can't find why this is wrong; please help me to find mistakes
this my code

Code: Select all

//117 The Postal Worker rings once
#include <iostream>
#include <string>
#include <cassert>
using namespace std;
const char dead[]="deadend";
#define N 40
#define LEN 1000
#define inf 99999999
int edge[N][N],degree[N];
int main(){
	//freopen("a.in","r",stdin);
	char st[LEN];
	int len;
	int _wer=0,sum=0,odd1,odd2,x,y;
	while(1){
		_wer=0;
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++) 
				edge[i][j]=inf;
		for(int i=0;i<N;i++) degree[i]=0;
		while(cin>>st){
			_wer=1;
			if(strcmp(st,dead)==0) break;
			len=strlen(st);
			x=st[0]-'a';y=st[len-1]-'a';
			if (edge[x][y]>len){
			edge[x][y]=len;
			edge[y][x]=len;
			}
			degree[x]++;
			degree[y]++;
			sum+=len;
		}
		if(_wer==0) break;
		int q;odd1=-1;odd2=-1;
		for(q=0;q<N;q++) if (degree[q]%2!=0){odd1=q;q++;break;}
		for(;q<N;q++) if(degree[q]%2!=0){odd2=q;break;}

		if(odd1!=-1 && odd2!=-1)
		{
			assert(odd1!=odd2);
			for(int i=0;i<N;i++) edge[i][i]=0;
			for(int k=0;k<N;k++){
				for(int i=0;i<N;i++){
					for(int j=0;j<N;j++){
						if (edge[i][k]+edge[k][j]<edge[i][j])
							edge[i][j]=edge[i][k]+edge[k][j];
					}
				}
			}
		cout<<sum+edge[odd1][odd2]<<endl;
		}
		else cout<<sum<<endl;
	}
	return 0;
}

Thanks.

[Darko]

Maybe reset sum to 0 *inside* the loop?

Btw, you should read other threads, someone had *exactly* the same mistake in their code. And if you missed it, you should've posted the question in one of those.

[Artikali]

Thank you very much, That was a stupid mistake of mine, i should be careful.

[mukeshtiwari]

hi everybody in problem statement it is give

The tour must begin and end at the same intersection.

it means that we have to find out euler tour .and euler tour is possible only when

An undirected graph contains an Eulerian cycle iff (1) it is connected and (2) each vertex is of even degree.

but problem statement also states that

There will be at most two intersections with odd degree.

in this situtation only euler tour is possible not cycle ..

An undirected graph contains an Eulerian path iff (1) it is connected and (2) all but two vertices are of even degree. These two vertices will be the start and end points of the path.

...now plz explain me the problem wheather we have to find euler cycle or euler tour ..becoz i think it is asking for cycle which is not possible when there will be odd virtex...

[helloneo]

...now plz explain me the problem wheather we have to find euler cycle or euler tour ..becoz i think it is asking for cycle which is not possible when there will be odd virtex...

Neither of them..
You can use the same edges several times..

[sohel]

So, basically it is a 'Chinese Postman' problem.

[mahan]

hi .. who can help me ? i got WA for this Q many time .. my Algorithm is very simple .. i add the edge weights and store them in sumEdges .. if there are 2 odd nodes , i find the min path between this 2 node with dijkstra algorithm , then add with sumEdges.. then print sumEdges ..

Code: Select all

[#include <iostream>
#include <string>
#include <fstream>

using namespace std;



const int Max=1000000; 
const int mx=10000;
const int bound=27;

int cost[bound][bound]={Max};
int sw[mx]={-1};
int i,j,k,count=0;

int dijkstra(int first,int last){
	sw[first]=1;
	int cur;
	int min=Max;

	for(j=1;j<bound;j++){
		min=Max;
		for(k=1;k<bound;k++){
			if(!sw[k]){
				if(cost[first][k]<min){ min=cost[first][k]; cur=k;}
			}
		}
		sw[cur]=1;

		for(i=0;i<bound;i++){
			if(!sw[i] && i!=first && i!=cur){
				if(cost[first][i]>cost[first][cur]+cost[cur][i]){
					cost[first][i]=cost[first][cur]+cost[cur][i];
				}
			}
		}
		if(cur==last) break;
	}
	return cost[first][last];
}


void main(){
		
	for(i=0;i<bound;i++){
		for(j=0;j<bound;j++){
			cost[i][j]=Max;
		}
	}
	
//	ifstream cin("117.in");

	char temp[1000];
	int firstNode,lastNode;
	int w=0;
	int l=0;

	while(1){
		cin>>temp;
		if(!strcmp(temp,"deadend")){
			w=0;
			firstNode=-1;
			lastNode=-1;
			int sumEdges=0;

			for(i=0;i<bound;i++){
				count=0;
				for(j=0;j<bound;j++){
					if(cost[i][j]!=Max){
						sumEdges+=cost[i][j];
						count++;
					}
				}
				if((count%2)){
					if(!w){
						firstNode=i;
						w=1;
					}
					else lastNode=i;
				}							
			}
			
			sumEdge/=2;
			
			if(firstNode!=-1)	sumEdges+=dijkstra(firstNode,lastNode);

			cout<<sumEdges<<endl;

			for(i=0;i<bound;i++){
				sw[i]=0;
				for(j=0;j<bound;j++){
					cost[i][j]=Max;
				}
			}
			continue;
		}
		else if(cin.eof()) break;
		int length=strlen(temp);
		l+=length;
		cost[temp[0]-'a'][temp[length-1]-'a']=length;
		cost[temp[length-1]-'a'][temp[0]-'a']=length;
		sw[temp[0]-'a']=0;
		sw[temp[length-1]-'a']=0;		
	}
}

thanx for ur attention

[toni]

hello everyone, My algorithm is sum up all the paths and if there exist two odd degree nodes, use the Bellman_Ford to find shortest path between theis two nodes.

I try several cases and this program can help me find the correct answer but , I still got WA.

Maybe I have some bugs in my program, I really need your help!

Can anyone give me some test datas? Or some advices ,thx!

[ani_mitr86]

When I tried to find the minimum distance by Bellman Ford it was giving WA. So, I tested if the graph is connected or not and I found that some unconnected graph is there contradicting the problem statement. so, there is a mistake in data set.