10171 - Meeting Prof. Miguel...

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Fri Aug 05, 2005 11:43 pm

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Thanks..

Post by helloneo » Thu Aug 11, 2005 5:14 pm

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

roni
New poster
Posts: 11
Joined: Tue Aug 09, 2005 11:57 am
Location: SUST, BANGLADESH
Contact:

10171 WA? I SOLVED THE PREV POST'S IO

Post by roni » Tue Sep 06, 2005 9:00 pm

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(SUST)

roni
New poster
Posts: 11
Joined: Tue Aug 09, 2005 11:57 am
Location: SUST, BANGLADESH
Contact:

Why WA 10171??

Post by roni » Fri Sep 09, 2005 5:07 am

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!!!!!!!!!
roni(SUST)

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Feb 17, 2006 10:22 pm

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
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

10171 WA

Post by snar » Mon May 29, 2006 7:59 am

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
Narek Saribekyan

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

10171,WA ples help

Post by turcse143 » Thu Mar 06, 2008 4:57 am

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?
''I want to be most laziest person in the world''

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Sun Mar 16, 2008 7:47 pm

hei, is there nothing anybody who check my code?
ples check it.
''I want to be most laziest person in the world''

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Sun Mar 16, 2008 8:47 pm

See jackie's post..

Your code fails on that test case.. :-)

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Fri Mar 21, 2008 11:01 pm

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?
''I want to be most laziest person in the world''

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 10171 - thanx Manzoor for a nice problem

Post by kbr_iut » Thu Jul 03, 2008 2:38 am

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.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 10171 - Meeting Prof. Miguel

Post by stcheung » Sat Oct 04, 2008 1:21 pm

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
New poster
Posts: 1
Joined: Fri May 15, 2009 6:34 am

Re: 10171 - Meeting Prof. Miguel

Post by waiyee422 » Fri May 15, 2009 6:44 am

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
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm
Location: Chittagong, Bangladesh

Re: 10171 - Meeting Prof. Miguel

Post by @li_kuet » Mon Jun 18, 2012 6:42 pm

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
New poster
Posts: 3
Joined: Thu Oct 18, 2012 11:03 pm

Re: 10171 - Meeting Prof. Miguel

Post by Raihan_SUST » Thu Oct 18, 2012 11:15 pm

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);
    }
}



Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest