## 10171 - Meeting Prof. Miguel...

Moderator: Board moderators

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
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
``````

Code: Select all

``````100 B
``````
Hope it helps.

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

### Thanks..

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

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

### 10171 WA? I SOLVED THE PREV POST'S IO

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
Contact:

### Why WA 10171??

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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

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

### 10171,WA ples help

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
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
See jackie's post..

Your code fails on that test case..

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 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''

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 10171 - thanx Manzoor for a nice problem

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

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

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

### Re: 10171 - Meeting Prof. Miguel

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

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

``````