10171 - Meeting Prof. Miguel...

[daveon]

Hi,

INPUT

Code: Select all

2
Y U A B 10
Y U A B 100
A B
0

OUTPUT

Code: Select all

10 B

YOUR CODE'S OUTPUT

Code: Select all

100 B

Hope it helps.

[helloneo]

Thank you.. I got AC..
It's so tricky..

[roni]

i build 2 different table for me, & Prof.
i update each road everytime by checking if it is smaller than previous.
Then i rum FW for both. Summing from 2 table, i out put the minimum.
i check some input from board. It out right.
Please someone check my logic & give some I/O or coding help.
--------Thanks, roni(SUST)

Code: Select all

#include<stdio.h>				// WA

#define INF -32768
#define MAX 27

#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)

long distance_pm[MAX][MAX], distance_sm[MAX][MAX], alpha_pm[MAX], alpha_sm[MAX];

void initial()
{
	long i, j;

	for(i = 0; i < MAX; i++)
		alpha_pm[i] = alpha_sm[i] = 0;

	for(i = 0; i < MAX; i++)
		for(j = 0; j < MAX; j++)
		{
			if(i != j)
			{
				distance_sm[i][j] = INF;
				distance_pm[i][j] = INF;
			}
			else
			{
				distance_sm[i][j] = 0;
				distance_pm[i][j] = 0;
			}
		}
}

void Floyd_Warshall()
{
	long i, j, k;

	for(k = 0; k < MAX; k++)
	for(i = 0; i < MAX; i++)
	for(j = 0; j < MAX; j++)
	{
		if(alpha_sm[i] && alpha_sm[j] && alpha_sm[k])
			distance_sm[i][j] = max(distance_sm[i][j], min(distance_sm[i][k], distance_sm[k][j]));

		if(alpha_pm[i] && alpha_pm[j] && alpha_pm[k])
			distance_pm[i][j] = max(distance_pm[i][j], min(distance_pm[i][k], distance_pm[k][j]));
	}
}


void main()
{
	long edge, w, i, temp, min;
	char type, dir, u, v, sahriar, miguel, mitting[MAX], m;

//freopen("E:\\test.txt", "rt", stdin);

	while(scanf("%ld", &edge) == 1 && edge)
	{
		initial();
		for(i = 0; i < edge; i++)
		{
			scanf(" %c %c %c %c %ld", &type, &dir, &u, &v, &w);
			if(type == 'Y')
			{
				alpha_sm[u-'A'] = alpha_sm[v-'A'] = 1;

				if(dir == 'U')
				{
					if(distance_sm[u-'A'][v-'A'] == INF || distance_sm[u-'A'][v-'A'] < -w)
						distance_sm[u-'A'][v-'A'] = -w;	
				}
				else
				{
					if(distance_sm[u-'A'][v-'A'] == INF || distance_sm[u-'A'][v-'A'] < -w)
					{
						distance_sm[u-'A'][v-'A'] = -w;
						distance_sm[v-'A'][u-'A'] = -w;
					}
				}
			}
			else
			{
				alpha_pm[u-'A'] = alpha_pm[v-'A'] = 1;

				if(distance_pm[u-'A'][v-'A'] == INF || distance_pm[u-'A'][v-'A'] < -w)
				{
					if(dir == 'U')
						distance_pm[u-'A'][v-'A'] = -w;	
					else
					{
						distance_pm[u-'A'][v-'A'] = -w;
						distance_pm[v-'A'][u-'A'] = -w;
					}
				}
			}
		}

		Floyd_Warshall();

		
		scanf(" %c %c", &sahriar, &miguel);
		min = INF;
		for(i = 0; i < MAX; i++)
		{
			if(distance_sm[sahriar - 'A'][i] != INF && distance_pm[miguel - 'A'][i] != INF)
			{
				temp = distance_sm[sahriar - 'A'][i] + distance_pm[miguel - 'A'][i];
				if(temp > min)
				{
					m = 0;
					min = temp;
					mitting[m++] = i + 'A';
				}
				else if(temp == min)
				{
					mitting[m++] = i + 'A';
				}
			}
		}

		if(min != INF)
		{
			printf("%ld", (-1)*min);
			for(i = 0; i < m; i++)
				printf(" %c", mitting[i]);

			printf("\n");
		}
		else
			printf("You will never meet.\n");
	}
}

[roni]

my code support all the input in this page. But, i get wrong answer.
i cann't know why? i choose 2 FW for both me and Prof. i think, i consider multiple edge. Can anyone tell my bug? any IO or help is helpfull.
if anyone want to see my code, i can post.
Please help!!!!!!!!!

[sclo]

I used Floyd to solve this one and got WAs. The thing to watch out for is that the input contains self loops with positive costs. Just simply ignore then when computing shortest path costs.

[snar]

Why WA?
Can anyone test my code?

Code: Select all

#include <stdio.h>
#define MAX 162500
#define N 26

int manzoor[N][N], profmiguel[N][N] ;

void main() {

	int m, c, min, i, j, k ;
	char p, q, u, v, a, b ;

	while ( scanf ( "%d", &m ), m ) {

		for ( i=0; i<N; i++ )
			for ( j=0; j<N; j++ )
				manzoor[i][j] = profmiguel[i][j] = i == j ? 0 : MAX ;
        
		for ( i=0; i<m; i++ ) {

			scanf ( " %c %c %c %c %d", &p, &q, &u, &v, &c ) ;

			if ( p == 'Y' ) 
				if ( q == 'U' )
                    manzoor[u-'A'][v-'A'] = c ; 
				else
					manzoor[u-'A'][v-'A'] = manzoor[v-'A'][u-'A'] = c ;            
			else		
                if ( q == 'U' )
                    profmiguel[u-'A'][v-'A'] = c ; 
				else
					profmiguel[u-'A'][v-'A'] = profmiguel[v-'A'][u-'A'] = c ; 		
		}
        

        for ( k=0; k<N; k++ )
			for ( i=0; i<N; i++ )
				for ( j=0; j<N; j++ ) {

					if ( manzoor[i][k] + manzoor[k][j] < manzoor[i][j] ) 
						manzoor[i][j] = manzoor[i][k] + manzoor[k][j] ;

					if ( profmiguel[i][k] + profmiguel[k][j] < profmiguel[i][j] ) 
						profmiguel[i][j] = profmiguel[i][k] + profmiguel[k][j] ;
				}			

		scanf ( " %c %c", &a, &b ) ;
		
		min = MAX ;
		for ( i=0; i<N; i++ )
            if ( manzoor[a-'A'][i] + profmiguel[b-'A'][i] < min )
					min = manzoor[a-'A'][i] + profmiguel[b-'A'][i] ;

		if ( min == MAX )
			printf ( "You will never meet.\n" ) ;
		else {

			printf ( "%d", min ) ;

			for ( i=0; i<N; i++ )
				if ( manzoor[a-'A'][i] + profmiguel[b-'A'][i] == min )
					printf ( " %c", i+'A' );

			putchar ( '\n' ) ;
		}		
	}
}

Thanks

[turcse143]

Here is code i got WA i don't know whats my problem.
ples help me.

Code: Select all

#include<stdio.h>
#include<string.h>
char source,source1,destination;
char destination1,direction,age;
int old[28][28],young[28][28],array[28],array1[28];
int old_path[28][28],young_path[28][28],data[28];

main()
{
	int n,i,j,k,p,a,b,c;
	int flag,val;
	int dis,dis1,cost,temp;
	freopen("10171a.in","rt",stdin);
	while(scanf("%d\n",&n)==1)
	{
		if(n==0)
			break;
		memset(array,0,sizeof(array));
		for(i=0;i<28;i++)
		{
			for(j=0;j<28;j++)
			{
				old[i][j]=10000000;
				young[i][j]=10000000;
				old_path[i][j]=0;
				young_path[i][j]=0;
			}
			old[i][i]=0;
			young[i][i]=0;
			old_path[i][i]=1;
			young_path[i][i]=1;
		}
		flag=0;j=0;c=0;
		for(p=0;p<n;p++)
		{
			scanf("%c %c %c %c %d\n",&age,&direction,&source,&destination,&val);
				a=source-65;
				b=destination-65;
				if(c<b)
					c=b;
				else if(c<a)
					c=a;

		

			if(age=='Y')
			{
				if(direction=='U')
				{
					young[a][b]=val;
					young_path[a][b]=1;
				}
				else
				{
					young[a][b]=val;
					young[b][a]=val;
					young_path[a][b]=1;
					young_path[b][a]=1;
				}
			}
			else if(age=='M')
			{
				if(direction=='U')
				{
					old[a][b]=val;
					old_path[a][b]=1;
				}
				else
				{
					old[a][b]=val;
					old[b][a]=val;
					old_path[a][b]=1;
					old_path[b][a]=1;
				}
			}
		}
		
		scanf("%c %c\n",&source1,&destination1);
		a=source1-65;
		b=destination1-65;
		if(c<a)
			c=a;
		else if(c<b)
			c=b;
	
		for(k=0;k<=c;k++)
		{
			for(i=0;i<=c;i++)
			{
				for(j=0;j<=c;j++)
				{
			
							dis=old[i][k]+old[k][j];
							if(old[i][j]>dis)
								old[i][j]=dis;
							old_path[i][j]=old_path[i][j]|(old_path[i][k]&old_path[k][j]);
				
				
							dis1=young[i][k]+young[k][j];
							if(young[i][j]>dis1)
									young[i][j]=dis1;
							young_path[i][j]=young_path[i][j]|(young_path[i][k]&young_path[k][j]);
					
				}
			}
		}

		for(i=0;i<=c;i++)
			array1[i]=i;
		for(i=0;i<=c;i++)
		{
			if(young_path[a][i]==0||old_path[b][i]==0)
				array[i]=-1;
			else
				array[i]=young[a][i]+old[b][i];
		}

	
		for(i=0;i<=c;i++)
			for(j=i+1;j<=c;j++)
			{
				if(array[j]<array[i])
				{
					temp=array[j];
					array[j]=array[i];
					array[i]=temp;
					temp=array1[j];
					array1[j]=array1[i];
					array1[i]=temp;
				}
			}
	

		flag=0;j=0;
		for(i=0;i<=c;i++)
		{
			if(array[i]!=-1&&flag==0)
			{
				cost=array[i];
				data[j]=array1[i];
				j++;
				flag=1;
			}
			else if(cost==array[i])
			{
				data[j]=array1[i];
				j++;
			}
			else
				continue;
		}
		if(flag==0)
			printf("You will never meet.\n");
		else
		{
			printf("%d ",cost);
			for(i=0;i<j;i++)
			{
				if(i==j-1)
					printf("%c\n",data[i]+65);
				else
					printf("%c ",data[i]+65);
			}
		}
		
	}
}

ples run my code. Is there any special input-output?

[turcse143]

hei, is there nothing anybody who check my code?
ples check it.

[helloneo]

See jackie's post..

Your code fails on that test case..

[turcse143]

I CHECK the jackie's input. here i have given some input output including
jackie's which is the last one.
ples check whats my fault.

Code: Select all

input:
4
Y U A B 4
Y U C A 1
M U D B 6
M B C D 2
A D
2
Y U A B 10
M U C D 20
A D
6
Y U A Z 0
Y U C A 0
Y U A Y 0
M U D Z 0
M B C D 0
M B C Y 0
A D 
2
Y U B D 0
M U B D 0
B B
2
Y U A B 0
M U A B 0
A C
2
Y U A B 0
M U A B 0
C C
2
Y U A Z 10
Y U A B 20
K K
2
Y U X Z 1
Y U X Z 10
X Z
2
M U X Z 1
M U X Z 10
X Z
2
M U X Z 1
Y U X Z 10
X Z
2
Y U A B 0
M U B A 10
A B
3
Y U A B 5
M B B C 5
M U B A 10
A B
3
Y U X Y 5
M B A Y 10
Y B X Y 10
X A
2
Y U A B 10
Y U A B 100
A B
0
output:
10 B
You will never meet.
0 Y Z
0 B D
You will never meet.
0 C
0 K
1 Z
You will never meet.
10 Z
0 B
5 B
15 Y
10 B
Press any key to continue

is it okk?

[kbr_iut]

actually I like to solve Manzoor's problem.As I need to focus myself 100% to the depth of the problem while solving.And amongst all problems I have ever solved, this problem actually made me crazy,,And who can tell me about the feelings exactly when i got AC on this problem,,,,,,,,,,,,,,,
Thanx Shahriar Manzoor for such kind of problems.

[stcheung]

turcse143: My AC program returns the exact same output as what you have above. I got AC after several tries, and I think all the tricky test cases have already been covered on pg 1 & 2.

Let me try recapturing them:
(0) use Dijkstra twice
(1) maintain 2 sets of edges, one for young and one for midage
(2) if there's already an existing road, then overwrite the cost only if the newer cost is smaller
(3) no need to worry about tracking multi-edges, because you will simply keep the one with smallest cost
(4) no need to worry about self-loop if you implement Dijkstra correctly
(5) if me & prof are on same city, do NOT immediately print out the city and move on. There may be other cities with cost of 0, which you will have to print out as well.
(6) if me and prof are both in a city that's not mentioned in the road descriptions, check whether we are in the same city before immediately printing out "You will never meet."

[waiyee422]

Could anyone help me find out why WA?

I tried all the test cases posted in here. Still got WA.

Code: Select all

#include <stdio.h>

const int MAX=30;
const int INF = 1000000;
int d_m[MAX+1];
int c_m[MAX+1][MAX+1];
int d_p[MAX+1];
int c_p[MAX+1][MAX+1];
bool flag[MAX+1];

void Dijkstra_m(int beg, int n)
{
	int i, j, u, tmp;
	for(i = 0; i <= n; i++)
	{
		d_m[i] = c_m[beg][i];
		flag[i] = false;
		
	}
	d_m[beg] = 0; flag[beg] = true;
	for(i = 1; i <= n; i++)
	{
		tmp = INF; u = beg;
		for(j = 1; j <=n; j++)
		{
			if(!flag[j] && d_m[j] < tmp)
			{
				u = j; 
				tmp = d_m[j];
			}
		}
		flag[u] = true;
		for(j  = 1; j <= n; j++)
		{
			if(!flag[j] && c_m[u][j] < INF)
			{
				if(d_m[u] + c_m[u][j] < d_m[j])
					d_m[j] = d_m[u] + c_m[u][j];
			}			
		}
	}
}

void Dijkstra_p(int beg, int n)
{
	int i, j, u, tmp;
	for(i = 0; i <= n; i++)
	{
		d_p[i] = c_p[beg][i];
		flag[i] = false;
		
	}
	d_p[beg] = 0; flag[beg] = true;
	for(i = 1; i <= n; i++)
	{
		tmp = INF; u = beg;
		for(j = 1; j <=n; j++)
		{
			if(!flag[j] && d_p[j] < tmp)
			{
				u = j; 
				tmp = d_p[j];
			}
		}
		flag[u] = true;
		for(j  = 1; j <= n; j++)
		{
			if(!flag[j] && c_p[u][j] < INF)
			{
				if(d_p[u] + c_p[u][j] < d_p[j])
					d_p[j] = d_p[u] + c_p[u][j];
			}			
		}
	}
}

int main()
{	
	int NoOfCon;
	char line[100];
	char buffer;
	char young, dir,start,sourse;
	int energy;
	char prof,me;

	while(1)
	{
		NoOfCon = 0;
		for(int i=0;i<=MAX;i++)
			for(int j=0;j<=MAX;j++)
			{
				c_m[i][j]=INF;
				c_p[i][j]=INF;
			}
		
		gets(line);
		sscanf(line,"%d",&NoOfCon);
			
		
		if(NoOfCon==0)
			break;
		

		for(int i=0;i<NoOfCon;i++)
		{
			gets(line);
			sscanf(line,"%c%c%c%c%c%c%c%d",&young,&buffer,&dir,&buffer,&start,&buffer,&sourse,&energy);
			if(young=='Y')
			{
				if(c_m[start-'A'+1][sourse-'A'+1]> energy)
					c_m[start-'A'+1][sourse-'A'+1] = energy;
				if(dir =='B')
					if(c_m[sourse-'A'+1][start-'A'+1] > energy)
						c_m[sourse-'A'+1][start-'A'+1]=energy;
			}	
			else
			{
				
				if(c_p[start-'A'+1][sourse-'A'+1] > energy)
					c_p[start-'A'+1][sourse-'A'+1]=energy;
				if(dir =='B')
					if(c_p[sourse-'A'+1][start-'A'+1]> energy)
						c_p[sourse-'A'+1][start-'A'+1]=energy;
			}
				
			
		}
		gets(line);
		sscanf(line,"%c%c%c",&me,&buffer,&prof);
		Dijkstra_m(me-'A'+1,MAX);
		Dijkstra_p(prof-'A'+1,MAX);
		
		int min=INF;
		char loca;
		bool first= true;
		int count = 0;
		char meet[MAX];
		for(int i=1;i<=MAX;i++)
		{
			if(d_m[i]<INF&&d_p[i]<INF && (min==INF || min>d_m[i]+d_p[i]))
			{
				count = 0;
				min = d_m[i]+d_p[i];
				meet[count] = i;
			}
			else if(min!= INF && min == c_m[me-'A'+1][i] + c_p[prof-'A'+1][i] )
				meet[++count] = i;

		}
		

		if(min!=INF)
		{
			printf("%d",min);
			
			for(int i =0;i <=count;i++)
			{			
				printf(" %c",meet[i]+'A'-1);
			}
			puts("");
		}
		else if(prof==me)
			printf("0 %c\n",prof);
		else
			printf("You will never meet.\n");
		

	}

	return 0;
}

Thanks.

[@li_kuet]

Try this Input :

Code: Select all

4
Y U A B 4
Y U C A 1
M U D B 6
M B C D 2
A D
2
Y U A B 10
M U C D 20
A D
6
Y U A Z 0
Y U C A 0
Y U A Y 0
M U D Z 0
M B C D 0
M B C Y 0
A D
2
Y U B D 0
M U B D 0
B B
2
Y U A B 0
M U A B 0
A C
2
Y U A B 0
M U A B 0
C C
2
Y U A Z 10
Y U A B 20
K K
2
Y U X Z 1
Y U X Z 10
X Z
2
M U X Z 1
M U X Z 10
X Z
2
M U X Z 1
Y U X Z 10
X Z
2
Y U A B 0
M U B A 10
A B
3
Y U A B 5
M B B C 5
M U B A 10
A B
3
Y U X Y 5
M B A Y 10
Y B X Y 10
X A
2
Y U A B 10
Y U A B 100
A B
0

Output should be :

Code: Select all

10 B
You will never meet.
0 Y Z
0 B D
You will never meet.
0 C
0 K
1 Z
You will never meet.
10 Z
0 B
5 B
15 Y
10 B

[Raihan_SUST]

Why All time WA???? :'( can't find the mistake....totally confused.... please help someone... :'(

Code: Select all

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <string>
#include <sstream>
#include <list>
#define MAXL 35
#define MAXS 1000010
#define MAXP 90000
#define INFIN 100000000
using namespace std;
#define PQ priority_queue
#define btc(x) __builtin_popcount(x)
#define MP(x, y) make_pair(x, y)
#define PAIR pair< int, int >
#define mem(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define pi (2*acos(0))
#define oo 1<<20
#define dd double
#define ll long long int
#define llu long long unsigned
#define ERR 1e-5
#define fst first
#define sec second
#define SZ(a) (int)a.size()
#define All(a) a.begin(),a.end()
#define FOR(i,p,k) for (i=p; i<k;i++)
#define REP(i,n) for (i=0;i<n;i++)
#define REV(i,n) for (i=n;i>=0;i--)

void dfs_y(int u);
void dfs_m(int u);
int dist1[MAXL][MAXL], n;
int dist2[MAXL][MAXL];
int color1[MAXL], color2[MAXL];
vector<int>edge_y[MAXL];
vector<int>edge_m[MAXL];
vector<char>ans;

int main()
{
    int i, j, k, res, indx, a, b, MIN, cst;
    char st, ed;
    char str[MAXL];
    while(scanf(" %d", &n)==1)
    {
        if( n==0 ) break;
        map<char , int>Input;
        map<int , char>Output;
        ans.clear();
        mem(str,0);
        for(i=0; i<MAXL; i++) edge_m[i].clear();
        for(i=0; i<MAXL; i++) edge_y[i].clear();
        indx = 1;

        for(i=0; i<MAXL; i++){
            for(j=0; j<MAXL; j++) {
                dist1[i][j] = INFIN;
                dist2[i][j] = INFIN;
            }
            dist1[i][i] = 0;
            dist2[i][i] = 0;
        }

        for(i=1; i<=n; i++)
        {
            scanf(" %[^\n]", str);
            if(!Input[str[4]]) {
                Input[str[4]] = indx;
                Output[indx] = str[4];
                indx++;
            }
            if(!Input[str[6]]) {
                Input[str[6]] = indx;
                Output[indx] = str[6];
                indx++;
            }
            if(str[0]=='Y')
            {
                if(str[2]=='U') {
                    if(Input[str[4]]==Input[str[6]]) cst = 0;
                    else cst = str[8]-'0';
                    dist1[Input[str[4]]][Input[str[6]]] = cst;
                    edge_y[Input[str[4]]].pb(Input[str[6]]);
                }
                else if(str[2]=='B') {
                    if(Input[str[4]]==Input[str[6]]) cst = 0;
                    else cst = str[8]-'0';
                    dist1[Input[str[4]]][Input[str[6]]] = cst;
                    dist1[Input[str[6]]][Input[str[4]]] = cst;
                    edge_y[Input[str[4]]].pb(Input[str[6]]);
                    edge_y[Input[str[6]]].pb(Input[str[4]]);
                }
            }
            else if(str[0]=='M')
            {
                if(str[2]=='U') {
                    if(Input[str[4]]==Input[str[6]]) cst = 0;
                    else cst = str[8]-'0';
                    dist2[Input[str[4]]][Input[str[6]]] = cst;
                    edge_m[Input[str[4]]].pb(Input[str[6]]);
                }
                else if(str[2]=='B') {
                    if(Input[str[4]]==Input[str[6]]) cst = 0;
                    else cst = str[8]-'0';
                    dist2[Input[str[4]]][Input[str[6]]] = cst;
                    dist2[Input[str[6]]][Input[str[4]]] = cst;
                    edge_m[Input[str[4]]].pb(Input[str[6]]);
                    edge_m[Input[str[6]]].pb(Input[str[4]]);
                }
            }
        }

        for(k=1; k<indx; k++)
            for(i=1; i<indx; i++)
                for(j=1; j<indx; j++)
                    dist1[i][j] = min(dist1[i][j], (dist1[i][k] + dist1[k][j]));

        for(k=1; k<indx; k++)
            for(i=1; i<indx; i++)
                for(j=1; j<indx; j++)
                    dist2[i][j] = min(dist2[i][j], (dist2[i][k] + dist2[k][j]));

        cin >> st >> ed;
        a = Input[st];
        b = Input[ed];
        mem(color1,0);
        dfs_y(a);
        mem(color2,0);
        dfs_m(b);
        MIN = INFIN;
        for(i=1; i<indx; i++)
        {
            if(color1[i] && color2[i]) {
                MIN = min(MIN , (dist1[a][i]+dist2[b][i]));
                ans.pb(Output[i]);
            }
        }
        sort(ans.begin() , ans.end());
        if(SZ(ans)>0)
        {
            cout<<MIN;
            for(i=0; i<SZ(ans); i++)
                cout<<" "<<ans[i];
            cout<<"\n";
        }
        else
            cout<<"You will never meet.\n";
    }
    return 0;
}

void dfs_y(int u)
{
    int i, j, v;
    color1[u] = 1;
    for(i=0; i<SZ(edge_y[u]); i++)
    {
        v = edge_y[u][i];
        if(!color1[v])
            dfs_y(v);
    }
}

void dfs_m(int u)
{
    int i, j, v;
    color2[u] = 1;
    for(i=0; i<SZ(edge_m[u]); i++)
    {
        v = edge_m[u][i];
        if(!color2[v])
            dfs_m(v);
    }
}