## 10171 - Meeting Prof. Miguel...

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10171 - Meeting Prof. Miguel

Try the I/O in the post before yours.
Check input and AC output for thousands of problems on uDebug!

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);
}
}
[color=#008000][/color]
``````

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10171 - Meeting Prof. Miguel

@li_kuet wrote: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
``````
Check input and AC output for thousands of problems on uDebug!

boy wang
New poster
Posts: 2
Joined: Fri Dec 07, 2012 4:22 pm

### Re: 10171 - Meeting Prof. Miguel

Hi,Can anybody help me with this problem? I got wa

First,I am sorry that i am not very good at english .

I hava tried all the test cases ,and the answer is ok. I am crazy,and the following is my code:

Code: Select all

``````#include <iostream>
#include <map>
#include <vector>
using namespace std;

const int inf=2000000000;

struct aim{
char c;
int w;
aim(char c0=' ',int w0=inf){
c=c0;
w=w0;
}
};

int n=0;
map < char,vector<aim> > youngmap;
map < char,vector<aim> > midmap;
map < char,int > youngdis,middis;
vector <aim> ans;

void initial(){
youngmap.clear();
midmap.clear();
youngdis.clear();
middis.clear();
ans.clear();
ans.push_back(aim(' ',inf));
}

void input(){
char yorm,uorb,from,to;
int wei;
for(int i=0;i<n;i++){
cin>>yorm>>uorb>>from>>to>>wei;
youngdis[from]=inf;
youngdis[to]=inf;
middis[from]=inf;
middis[to]=inf;
if(yorm=='Y'){
youngmap[from].push_back(aim(to,wei));
if(uorb=='B') youngmap[to].push_back(aim(from,wei));
}
if(yorm=='M'){
midmap[from].push_back(aim(to,wei));
if(uorb=='B') midmap[to].push_back(aim(from,wei));
}
}
}

void bellford(){
int nsize=youngdis.size();
char youngs,mids;
cin>>youngs>>mids;
youngdis[youngs]=0,middis[mids]=0;
map < char,int >::iterator it;
while(nsize--){
for(it=youngdis.begin();it!=youngdis.end();it++){
char s=it->first,d;
for(int i=0;i<youngmap[s].size();i++){
d=youngmap[s][i].c;
if(youngdis[d]>youngdis[s]+youngmap[s][i].w){
youngdis[d]=youngdis[s]+youngmap[s][i].w;
}
}
for(int i=0;i<midmap[s].size();i++){
d=midmap[s][i].c;
if(middis[d]>middis[s]+midmap[s][i].w){
middis[d]=middis[s]+midmap[s][i].w;
}
}
}
}
}

void computing(){
map < char,int >::iterator it;
bellford();
for(it=youngdis.begin();it!=youngdis.end();it++){
//cout<<"young->"<<it->first<<ends<<it->second<<endl;
//cout<<"mid->"<<it->first<<ends<<middis[it->first]<<endl;
if(middis[it->first]<inf&&it->second<inf){
if(middis[it->first]+it->second>ans[0].w)  continue;
if(middis[it->first]+it->second<ans[0].w)  ans.clear();
ans.push_back(aim(it->first,middis[it->first]+it->second));
}
}

}

void output(){
if(ans[0].w>=inf){
cout<<"You will never meet."<<endl;
return;
}
cout<<ans[0].w;
for(int i=0;i<ans.size();i++)
cout<<" "<<ans[i].c;
cout<<endl;
}

int main(){
while(cin>>n&&n){
initial();
input();
computing();
output();
}
return 0;
}
``````
so can anybody find my mistake or give me a case? my email address : wangtaoboy@foxmail.com

Thank you!!!!!!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10171 - Meeting Prof. Miguel

Input:

Code: Select all

``````1
M U A B 100
C A
0``````
AC output:

Code: Select all

``You will never meet.``
Check input and AC output for thousands of problems on uDebug!

boy wang
New poster
Posts: 2
Joined: Fri Dec 07, 2012 4:22 pm

### Re: 10171 - Meeting Prof. Miguel

brianfry713 wrote:Input:

Code: Select all

``````1
M U A B 100
C A
0``````
AC output:

Code: Select all

``You will never meet.``
Hi, I have found my mistake before this , and I hava gotten accepted.I made some mistake in initial and thaks anyway.
void initial(){
youngmap.clear();
midmap.clear();
youngdis.clear();
middis.clear();
ans.clear();
ans.push_back(aim(' ',inf));
for(char ch1='A';ch1<='Z';ch1++){
middis[ch1]=inf;
youngdis[ch1]=inf;
}
}

elexhobby
New poster
Posts: 2
Joined: Sat Aug 24, 2013 2:54 am

### Re: 10171 - Meeting Prof. Miguel

I have tried all the cases mentioned in these 4 pages, and I get the expected output on all of them. I still get a WA when I submit though. Could somebody please help me?

Code: Select all

``````#include<utility>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<map>
#include<vector>
#include<set>
#include<algorithm>
#define M 100000
#define tr(c,i) for(typeof(c.begin()) i=c.begin(); i!=c.end(); ++i)
using namespace std;
typedef map<char, vector<pair<char,int> > > Graph;
typedef pair<int,char> ic;
typedef pair<char,int> ci;

void buildGraph(int n, Graph &my_graph, Graph &prof_graph, char &mycity,
char &profcity) {
for (int i=0; i<n; ++i) {
char age, direction, start, end;
int distance;
cin>>age>>direction>>start>>end>>distance;
if (age=='Y') {
my_graph[start].push_back(make_pair(end,distance));
if (direction=='B') {
my_graph[end].push_back(make_pair(start,distance));
}
else {
my_graph[end];
}
}
if (age=='M') {
prof_graph[start].push_back(make_pair(end,distance));
if (direction=='B') {
prof_graph[end].push_back(make_pair(start,distance));
}
else {
prof_graph[end];
}
}
}
cin>>mycity>>profcity;
}

void exploreGraph(Graph &graph, map<char,int> &F, set<pair<int,char> > &Q,
map<char,int> &D) {
pair<int,char> top = *Q.begin();
Q.erase(Q.begin());
char cur_city = top.second;
char cur_distance = top.first;
F[cur_city] = cur_distance;

tr(graph[cur_city],i) {
char to_city = i->first;
int cost = i->second;
if (D[to_city]>D[cur_city]+cost) {
if (D[to_city]!=M) {
Q.erase(Q.find(ic(D[to_city],to_city)));
}
D[to_city] = D[cur_city]+cost;
Q.insert(ic(D[to_city],to_city));
}
}
}

int main() {
int n;
cin>>n;
while (n) {
Graph my_graph,prof_graph;
char mycity, profcity, my_new_node, prof_new_node;
map<char,int> my_D, prof_D; //temporary distances
map<char,int> my_F, prof_F; //final distances
set<pair<int,char> > my_Q, prof_Q; //acts as priority queue
buildGraph(n, my_graph, prof_graph, mycity, profcity);
tr(my_graph,i) {
my_D[i->first] = M;
}
tr(prof_graph,i) {
prof_D[i->first] = M;
}
my_D[mycity] = 0;
prof_D[profcity] = 0;
my_Q.insert(pair<int,char>(0,mycity));
prof_Q.insert(pair<int,char>(0,profcity));
while (!my_Q.empty()) {
exploreGraph(my_graph,my_F,my_Q,my_D);
}
while (!prof_Q.empty()) {
exploreGraph(prof_graph,prof_F,prof_Q,prof_D);
}

set<ic> common_cities;
map<char,int>::iterator i=my_F.begin(), j=prof_F.begin();
while (i!=my_F.end() && j!=prof_F.end()) {
if (i->first==j->first)  {
common_cities.insert(ic(i->second+j->second, i->first));
i++;
j++;
}
else if (i->first<j->first)
i++;
else
j++;
}

if (common_cities.empty())
cout<<"You will never meet.";
else {
set<ic>::iterator i=common_cities.begin();
cout<<i->first;
while (i->first==common_cities.begin()->first &&
i!=common_cities.end()) {
cout<<" "<<i->second;
i++;
}
}
cout<<endl;
cin>>n;
}
return 0;
}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10171 - Meeting Prof. Miguel

Input:

Code: Select all

``````4
Y B R L 386
M B B Q 386
M B R A 27
Y U K K 40
D I
10
Y B C S 282
M U M J 135
Y U X R 69
Y B L B 42
Y U S F 284
M B Y B 370
M U Y D 456
Y U P X 281
Y B E R 336
Y U P M 357
F Q
15
M B O H 364
Y U O C 276
M U N W 151
M U H W 176
M B B G 86
Y B L C 434
M U S V 402
Y B Q K 301
Y U X I 189
Y B R R 31
M B T P 175
M B W F 497
Y U M J 183
M B R D 232
Y U F O 368
N C
19
Y B H Q 245
Y U A S 379
M U Q P 350
Y U H E 124
M B F V 491
Y U N L 432
Y U P K 407
M B J R 29
Y U Z T 428
Y B B C 276
M U C I 38
Y B N E 128
Y U F M 496
M B W D 490
M U X P 90
Y U U K 169
Y U C L 7
M B H W 122
M B O I 68
D R
2
M U V K 230
M B S G 444
Q O
19
M U O B 424
M B N W 36
Y B N X 468
Y U G D 430
Y U R T 199
Y U S N 273
M U G U 426
Y U Q O 184
Y U B U 445
Y B Y K 412
M B C A 336
Y B M V 301
Y U R D 319
M B N M 311
M U K U 127
Y U L M 224
M U K U 130
Y U X B 350
M B E M 140
Y E
11
M U R D 209
Y B A I 155
M B G O 273
Y B M F 142
Y B I V 121
M U V U 254
M B Y O 202
M U L U 368
Y U U M 458
M B Z H 248
M U F C 390
G P
7
Y U B B 288
M B R Z 33
Y U A X 186
M U F D 188
M U U R 414
M U I G 27
Y B P B 294
Q E
4
Y U H P 0
M B A N 151
Y B C D 215
Y B T D 464
M B
19
M B P P 471
Y U N X 292
Y B G S 390
M U X I 326
Y B J F 117
Y B U V 190
Y U Y U 234
M U B E 114
M U Q I 386
M B Y G 416
M B E Z 290
M B V Z 131
M U B E 386
Y B U F 412
Y U D X 274
M U G I 487
M U H E 284
Y B D Z 349
M B R L 18
N F
10
M B Q T 483
M B S B 471
Y U S H 438
M U P P 157
Y B D P 199
Y B T O 122
Y U W C 462
M B X F 57
Y B D J 491
M U E G 37
D V
17
M B J I 16
Y U A Y 404
Y B W E 470
Y U G Y 185
Y U X J 207
M U I P 411
M B D Z 318
Y B U D 211
Y U F A 455
M U Q P 418
M U F I 217
M B D Y 93
M B V V 314
M U Z C 275
Y B G J 294
M B T V 191
Y U E N 425
P S
16
Y U I U 90
Y B L X 161
M U H N 104
Y B A P 3
Y U F C 449
M B D C 177
Y U O Z 36
Y B U G 342
M B S C 270
M U E X 40
Y U O J 63
M B W H 214
M U M B 82
M U G K 443
Y B E A 159
M U E V 348
P Q
2
M B R L 457
Y B F Y 269
H R
20
M U J S 228
M B A G 308
Y B U B 398
M U M I 59
Y U Q J 109
Y U K V 53
Y B X R 426
Y B C W 231
M U E N 350
Y U P B 131
M B G P 81
Y U F B 181
Y B I Q 404
Y U N Y 32
M B F E 57
Y U U V 297
Y U W P 309
Y U W T 266
M U P U 185
M U C G 83
N U
9
M U M L 339
M U N T 118
Y U F E 121
M B X E 315
Y B E P 222
Y B N Q 327
M B Q E 149
M B P G 388
Y B Q Z 476
J P
18
Y B X A 66
M B M W 368
M U S M 305
Y B O F 308
Y U X W 172
M B O N 497
M B W T 421
M B V N 421
M B K C 261
Y U U O 352
M B V Y 217
Y B U W 351
M B X X 172
M U V C 371
Y B I A 341
Y B R H 69
Y U C Y 112
M U E L 364
X H
2
M U B M 412
M B W Q 456
S H
7
Y B N B 386
Y U J V 152
Y U J J 109
Y B Z Z 48
Y B D X 198
Y B G Q 468
M B O P 286
X V
2
M U I V 490
Y U M C 75
J L
5
Y U T G 469
M U B H 19
Y B I V 481
M U N S 412
M B W M 131
D I
18
M B H M 487
M U R B 125
M U E H 141
M B M T 393
M U E D 29
M B G R 424
Y B I I 10
Y U X I 140
Y U Q R 493
M U J B 190
M B X H 421
M U Z F 243
Y U B Y 154
Y B Q L 210
Y B A H 87
M U Y L 351
M B D Z 86
Y B K J 381
L C
14
M U K R 143
M B P B 124
M B F U 353
Y B C J 233
M B N R 435
Y U J M 487
Y U Q H 110
M U R D 57
Y B B E 321
M B W M 361
Y B D W 45
M U F S 89
M B E E 294
M U J U 417
K S
15
Y U Z R 123
Y B R V 312
Y B P A 156
Y B P T 422
M B G Y 301
Y B A X 425
M U C G 27
M B J K 196
Y U S W 499
Y B V O 141
Y U P Y 198
Y U L U 131
Y B M Z 346
M U A F 40
Y U C P 158
A C
20
Y B R D 111
M U R Y 42
Y U Z C 96
M U Q V 257
Y U J C 332
Y B C V 135
M U A M 437
Y U G Z 301
Y B T A 496
Y U W P 304
Y U J F 251
Y U K V 204
M B Z H 79
Y B D P 131
Y B M N 28
Y B G L 81
M U E K 143
M U S Y 180
Y U N O 463
Y U M M 179
O A
14
M B G D 466
Y B Q K 16
Y U T V 400
Y U B X 35
Y U K Z 154
Y B M A 325
M B S N 133
M B Y V 185
M B T X 329
Y B N G 316
M U A I 486
M B S L 129
M U Z F 15
M U M N 347
L K
4
Y U F E 100
M U O M 482
M B O H 18
Y U F C 46
S E
13
Y U M H 34
M U O T 96
Y U N V 382
M B F J 343
M B K W 481
Y U I R 441
M U Q M 208
Y U L S 163
M U S C 487
M U B D 193
M U S B 293
Y B W T 475
Y U B N 373
P V
20
Y U Y X 477
M B S X 346
M B Z B 411
M U H T 293
M U E R 371
M B R K 383
M B Z K 67
Y B F O 457
Y B J O 190
Y U Y A 335
M B I B 255
Y U A A 153
Y U N D 204
M B P F 326
M B O L 228
Y U T V 20
M U V F 116
M B Z J 11
M U X Q 362
Y B D Q 468
M D
14
M B Z T 57
Y U K E 44
M U K Z 355
Y B E F 259
Y U V H 138
M B V S 422
M B B X 280
M U M W 320
Y U Z L 4
M U M T 394
Y B S S 60
Y U P G 365
M U I Q 363
M B Q S 333
D Q
10
M U Q N 128
Y B R Q 105
M U I U 367
Y U M V 199
Y B F U 332
M U L V 169
M B M G 139
Y B A Q 280
Y B A Y 243
M U A U 288
L N
4
Y U C A 461
M U U I 63
M U W A 142
M U W S 185
G W
6
Y B Z A 284
M U I A 235
Y B Y E 486
M U B Q 12
M B G G 372
Y U R H 76
X Q
15
M B L M 282
Y B Q P 15
M U I K 224
Y U Q M 292
M B V J 141
Y B I A 260
M B N X 416
Y B R E 17
M B X I 174
Y U H J 476
Y B G N 36
Y U R Q 316
Y B W G 486
Y B X G 466
M U H F 446
I A
18
M B I W 95
M B B M 208
M U D Z 190
Y B Z N 169
M B S Q 351
Y U Y T 188
M U A J 114
M B I N 82
Y U D F 277
Y B C U 235
Y B K M 229
Y U R R 28
Y U E S 266
Y B E G 36
M B A C 238
M B Q B 335
M U A Q 250
M U Z E 79
L V
18
M U W H 105
Y U J P 472
M B P B 132
Y U S V 58
M U T Q 82
Y U E K 433
Y B D T 407
Y U M J 313
M B B Q 335
Y U P D 7
M U N W 128
Y B B T 199
M B E Z 90
Y U S W 8
Y U T W 233
M U U Y 251
Y U W H 223
M U A P 445
O L
8
M B O S 295
M B T K 340
M U Z Q 195
M U Q L 67
Y B B U 290
M U P R 55
Y B C F 151
M U N T 448
D V
3
M B C J 334
Y B Q D 164
M U I K 233
I Z
19
Y B Q O 10
Y U C E 294
Y B J B 385
Y U J K 380
M B M P 144
M B G Q 286
Y U O S 352
Y B G U 13
Y U U I 207
Y B L C 107
M U A Z 272
M U M I 308
M B W E 485
M B L J 251
Y U D M 448
Y U H K 150
Y B E U 388
M B R X 218
Y B O C 361
R F
15
Y U N W 130
M U O U 126
Y U L S 141
M U Y L 139
Y B U H 123
Y U S G 283
M U U E 393
M B U Q 289
M U H Q 237
M U T E 458
M U F P 54
Y U L J 260
Y U D V 318
M U L L 277
Y B X Z 186
J D
18
M B R H 89
Y U D D 24
M U O D 114
M B W H 132
M B Z X 225
Y B M U 286
Y B M A 483
M U J X 315
M U R I 180
M B R E 35
M B D X 242
M U F J 256
M B N V 406
M B S M 44
M B M X 238
M U Q S 18
Y U F Y 442
M U U E 135
F G
16
M U O E 347
Y U U N 202
Y U X R 386
M U T S 489
M U D O 350
Y U O K 319
Y B X B 253
Y B B D 425
M B M T 180
M B Q E 22
M U I U 29
M U W O 448
Y B X Y 304
M U X D 119
Y B K G 270
M U B H 350
J W
7
M B G A 68
Y B K D 303
Y U Z I 469
M U E O 64
M U R Z 376
M B J Y 59
M U I X 23
R Y
17
M B T K 230
M U I U 242
M U F J 22
M B T A 328
M B I K 126
M U U V 168
M U Y C 174
Y B U W 239
Y B A T 334
Y B X I 46
Y U M J 37
Y U Q C 300
Y B B B 437
Y B D A 221
Y U A A 210
M U R F 393
M B U U 117
D P
7
M U F V 109
M U F S 495
M B A E 313
Y U P A 260
M U T W 317
M U W L 49
M U N M 5
T M
5
M U L E 361
M B O K 327
M U V P 309
Y U E U 2
M U X M 203
W N
14
M U N Q 371
Y B G X 10
M B X D 54
M U G S 324
Y U W Q 139
M U D A 277
M U O H 380
M U Z Q 494
M B L M 488
Y U I D 193
Y U G Z 360
M U R O 459
Y U G P 337
Y B X O 46
R F
14
Y U L A 70
Y U S K 339
M B A K 368
Y U X A 467
Y B Y M 71
Y B K U 255
Y B P T 73
M U B M 492
M U R L 460
M U W H 361
M B C T 477
M B C L 287
M U H Z 279
Y U E A 109
P L
19
Y B Y D 160
Y U D M 329
Y B O A 215
Y U Z I 368
Y B B Q 462
Y B I M 458
M U I X 434
M U E J 327
Y U W K 494
M U L S 53
M U V Q 355
Y U Q E 160
M B Y K 45
Y B G B 107
Y U P J 106
Y U G H 2
Y B H Z 392
Y B C X 411
M U J W 323
T G
12
M U I Q 150
Y U P S 388
Y U Q U 295
Y B T P 141
Y U O O 329
Y U P A 316
M U O W 350
Y B G A 274
Y B N F 399
Y U E Y 61
Y U A Z 469
M U C I 295
W Z
19
Y B Y W 429
M B Q P 108
M U J K 215
Y B U U 335
Y B X T 422
Y U R N 207
Y B H O 389
M U M H 456
M B G G 130
M U T J 46
Y B N I 8
Y B I M 130
Y B D K 403
M B W L 156
Y U S X 370
Y B E Q 284
Y B N C 94
M B E F 309
M U Y N 235
W N
12
Y B P J 445
Y U E D 143
Y U Y N 204
M B H X 8
Y U Q Q 267
M B V A 240
Y U I O 223
M B W W 89
Y U L H 367
Y U Q G 365
Y U T V 20
Y U Z C 331
T V
20
M U O I 291
M B E V 166
Y U V V 473
Y B G E 337
Y B C T 362
Y B E X 207
Y B B G 105
Y B A Z 39
Y U C E 91
Y U F Q 108
Y B T Q 77
M B P P 192
M B W Y 370
Y U P S 475
Y B L J 438
Y U D D 176
M U I D 499
Y U F Q 81
Y U O C 325
Y B D V 416
M K
19
M U Y L 440
Y U H C 349
Y B Y G 169
M B O N 375
M U D V 172
M B S Y 443
M U X P 426
M U E I 289
Y U X O 424
M U Y P 140
Y U L R 222
M U V D 450
Y U O C 387
M U P T 32
M U I G 243
Y B K C 337
M U G I 398
M B F U 347
Y B Y I 163
F F
15
M U E A 114
Y B D I 270
Y B C Z 439
Y B L F 304
Y B V S 408
M B U L 72
M B U A 446
Y U O Z 269
M B I X 155
Y U W R 283
Y B D S 211
M U A T 252
M B Y J 87
M B X U 252
M U B Y 404
F S
20
Y B I H 156
Y U P M 322
M U C X 61
M B G A 496
M U Z C 435
M U G C 46
M U R M 482
Y U Q E 351
M U A B 430
Y U O C 130
Y B N V 72
M U M O 160
Y B Z C 492
M B Z G 75
Y U S R 324
M U W K 80
M B Y E 325
Y B E L 371
Y B O P 32
M U L S 3
L E
6
M U Z N 152
M U A A 195
M U U Z 92
Y B Y D 132
Y B Y G 82
M B P H 433
N U
7
Y U K T 485
M B A V 82
M B J V 458
M B V M 167
Y B V S 441
M B W Y 420
Y U H C 402
C D
9
M B M P 125
M U N W 179
Y U F Z 190
Y B T N 310
M B Z W 7
Y U V N 489
M U F P 377
M U N X 197
Y U F R 455
D Z
17
M B Z S 356
Y U O I 397
Y B K W 126
Y B B X 277
M U Z T 498
Y B L Q 42
M B L Z 323
M U S C 469
Y U I C 305
M U Z R 227
Y B Y P 236
Y U T B 484
M U G V 201
M B Y E 331
Y U Y B 46
M U U R 491
Y B H S 497
J M
2
Y U A F 1
Y B Z B 202
P Y
6
Y B B S 468
M B P A 260
Y B B R 370
M B C Z 297
M U J V 280
Y B D Q 259
V G
10
Y U U C 319
M U Z J 143
M U N P 139
Y B V P 293
M B J I 452
M B F Y 67
Y U Y F 244
Y B A J 327
M U B G 376
Y U O J 271
R B
16
Y B L I 56
M U B V 14
Y B T W 453
M B R I 289
Y B M V 92
Y B M Y 322
Y U Z Q 245
M B M E 70
M B Y J 424
M U Y E 177
M U D Q 306
M U A D 418
Y U Y X 255
M U N Z 378
M B T T 215
Y B J T 479
V T
11
Y B O W 486
Y B J H 486
M U O B 72
Y B N E 340
M U C H 204
Y U T B 93
Y B T C 37
M B V J 190
Y U W R 196
M B Y U 310
M B V W 385
O X
8
Y U O U 282
Y B M P 337
M B R L 361
M U Y C 19
Y B M B 88
Y U P X 169
Y B I V 305
M B I F 469
F H
12
M U A Q 207
M U T E 328
M B H T 451
M U G R 369
M B H B 162
Y B V S 40
Y U Q C 200
M B Z S 290
M B M N 13
M U T Q 360
Y B B C 54
Y B U J 78
Z T
8
M U I U 311
M B H F 414
M B U O 263
M U E M 10
Y U Q R 450
M B O Z 454
Y U U T 37
Y U Y Y 273
L T
7
M B Q M 149
Y B P D 179
M B A T 497
Y B S A 146
Y U O H 95
Y U D S 313
Y B R X 473
A Q
19
M U F D 93
Y B S H 487
M U D T 277
M U M C 299
M U Z Q 365
M U R J 392
Y B P R 423
M U O O 4
Y B J V 252
Y B B W 289
M U Z Q 455
Y U G R 319
Y B T I 474
M B F Z 222
M U F P 225
Y U Q S 437
M B K E 217
Y U T M 466
M U F G 403
S W
18
M B X J 55
Y U U D 493
M U P Q 319
M B Z J 271
M B T U 330
M U S F 160
M B J B 300
M U E M 412
M U P T 153
Y U N R 391
M U X D 109
M U C G 223
Y B I C 118
M U Y Z 228
M B Z Q 228
Y B C X 145
Y U M G 5
Y B T Z 433
N A
4
M U J A 478
Y B K H 275
M B F R 447
M U X M 37
M M
6
Y U D O 109
Y B F V 221
M B B F 396
Y B L C 49
M U J O 153
Y B W P 405
U E
18
Y U B C 343
M U W Z 192
Y B T V 74
M B V I 334
Y B A A 10
M B S O 435
M B M K 60
Y U X T 11
Y U O I 59
M U E F 361
M B E P 386
Y U V G 121
Y U V A 91
Y U I F 349
M B X V 91
Y B Z C 201
M U C D 211
Y B S H 260
N D
16
M B O H 218
Y B C J 478
Y U B O 451
Y B E V 368
Y U N T 200
Y B C A 194
Y U Y I 120
M U N R 260
M B F S 408
M U K X 38
M U A M 381
M B I G 143
M B A N 127
M U Z M 119
Y U U I 187
M B C U 219
I J
7
Y U V I 421
Y B H Z 261
M U V E 13
Y B V D 414
M U R G 455
Y U Z X 365
Y U Q R 103
M H
18
Y B Y T 86
M B S J 415
M U A Y 239
M U F J 165
M B Q X 246
M B Y A 268
M B J H 175
Y U R A 486
M U N R 372
Y B H D 494
M B Q F 343
M B Y P 189
Y B P O 356
M B X G 467
Y B A V 34
M B G T 150
M U Z A 61
M U Z Z 24
L I
17
M B R I 235
Y U Z K 296
Y B I H 121
M B X M 418
M B W J 145
M U O R 200
M B L D 74
Y U K T 37
M B H F 329
Y B U P 122
Y B Q G 207
Y B T B 115
Y U N C 247
M U B M 447
Y B Y P 56
Y B G V 142
Y U L M 327
J N
20
M B E A 386
M B K O 385
M B S J 477
M B R Z 142
M B B C 22
M U J X 491
Y B L K 226
Y B D E 213
M U Y O 167
Y U D Q 277
M B T S 281
M B J Q 43
M B C Z 104
M B R W 35
M B M C 270
M B T G 202
M U T T 116
M U K N 357
Y U G G 254
M B K B 178
S K
4
Y B D X 376
Y B F K 102
M B Z L 88
M B J Q 401
X R
3
Y B Y Z 91
M U Y N 290
M U R Z 484
J Y
6
Y U T W 173
Y U G S 312
M U F T 201
M B S F 151
Y U G X 18
M U L Z 257
V E
2
M U G X 167
Y B H A 418
V O
11
Y U I B 341
M B C F 376
M B T A 385
M B T Y 286
Y B O D 477
M B Z A 15
M B Z C 209
M U R Z 12
Y B C E 240
Y U G V 321
Y U Y I 484
P C
17
M U U A 427
M B Q R 475
M B T S 57
M U F F 167
Y B V T 311
M U Y L 482
Y U C D 420
Y U O L 272
Y B X G 238
Y U W Z 427
Y U G O 193
M U T O 435
Y U R E 409
Y U I E 274
M U J L 241
M B N H 24
M B W W 15
R D
12
Y U X Z 198
M B A Q 253
Y U X I 231
M B J J 264
M U A I 371
M U W J 442
M B D Y 279
Y B I U 379
Y U H U 119
M U E L 432
Y B E L 188
Y U W V 232
O Z
11
Y B Q T 150
Y U O X 233
Y U O I 224
Y B R O 468
Y B Q O 169
M U L Q 259
M B Z U 329
M U F E 468
Y B T A 440
M U T H 476
Y B Q D 207
E C
12
Y U H U 373
M U X F 102
Y U U A 480
Y U G R 417
Y U D M 233
M U A O 66
Y U N N 323
M B U S 416
Y B R D 290
M U B Q 60
M B G D 68
Y U S D 492
E M
9
Y B F O 149
Y U Z G 364
M U V J 268
M U U M 316
Y B U L 323
Y U Q B 402
Y U W C 377
Y U O O 63
Y U G X 131
S I
19
M U M W 459
M U Z J 118
M U U U 173
Y B E N 80
M B C F 266
M B M Q 157
M U H W 466
M U P E 113
M U S H 260
Y B V Q 127
M B W R 104
Y B E M 93
Y U E Z 363
Y U Z R 92
M B S E 441
Y B W K 448
Y B A W 271
Y B N M 241
M U C I 174
J X
14
Y B I L 42
Y B V T 395
Y U N Z 261
M U W R 131
M B J U 333
Y B L E 310
Y B C M 72
Y U E U 319
Y B U J 152
Y B I M 95
M U J A 420
Y U M M 491
M B J J 245
M B Y A 167
L T
20
Y B O I 468
Y B M B 440
Y U L L 23
M U W L 187
Y B A J 348
M B B E 368
Y U A L 22
M B Y P 197
Y B P I 37
Y U I O 242
Y U C U 498
Y B E I 110
M U R S 110
Y U B U 276
M U Q T 81
Y B X M 73
Y U T D 286
M B V M 35
Y B Y T 154
Y U L L 148
P T
18
M U F O 393
M U Z T 490
Y U L T 489
M U J L 226
Y U X E 443
Y U T E 353
Y B J R 154
M B K A 236
M B T E 424
Y U F D 373
M B T U 245
M U S Y 187
Y B X U 109
M U R H 102
Y B X I 398
Y B I K 361
Y B T I 415
M B T A 479
O Z
13
M U P N 146
M B P K 181
Y B Z M 150
Y B Y A 141
M U G U 379
Y B A B 390
M B H Y 112
Y U X C 447
M B S G 107
Y B M A 115
M U B I 49
Y B N I 241
Y B J B 228
R W
18
M U B L 81
M U E F 67
Y U N D 86
M U V A 367
Y U V O 352
Y B K E 115
M B I A 44
M U U E 442
Y B T B 380
Y B V G 214
Y U L N 427
M B J J 460
M B Q V 264
M B I R 275
M B B B 68
M B B B 398
M B T A 472
M U O N 78
O E
4
Y U B D 253
M B X Z 161
Y U W G 266
Y B N P 389
K G
2
M B H A 251
Y B Y B 152
L Z
9
M U B K 331
M B K F 27
Y B C M 444
M B U W 488
M U W C 136
M U N Z 128
Y U Y H 133
M U K V 160
M B G I 193
L H
9
Y B O B 329
M B J X 296
M B K F 446
M U T L 370
Y B C V 244
Y B Z G 312
M B U V 239
Y B C U 380
Y B K K 148
V Y
18
Y B Z S 305
M U S C 434
Y B E G 142
Y U H V 244
M U U M 177
M U D X 466
Y U M T 58
M U V Y 283
Y U S O 412
Y B W M 445
M B D O 203
Y U X N 265
Y U L B 246
M B V G 166
Y U Q L 309
M U M Z 169
Y U V F 391
Y B C J 377
P U
0
``````
AC output:

Code: Select all

``````You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
682 Y
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
260 A
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
837 T
You will never meet.
You will never meet.
You will never meet.
20 V
You will never meet.
0 F
You will never meet.
371 E
244 N
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
0 M
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
You will never meet.
``````
Check input and AC output for thousands of problems on uDebug!

elexhobby
New poster
Posts: 2
Joined: Sat Aug 24, 2013 2:54 am

### Re: 10171 - Meeting Prof. Miguel

Thanks brianfry713! I got AC.

cosmin79
New poster
Posts: 11
Joined: Fri Aug 09, 2013 7:25 pm

### Re: 10171 - Meeting Prof. Miguel

Could anyone take a look at my source code or give me some more tests? I'm passing all the test cases on those 4 pages in the forum, but I still manage to get WA. I've checked for everything I could think of (multiple edges between nodes, self loops, 0 cost edges etc). Thank you!

Code: Select all

``````#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <queue>
#define NMAX 26
#define INF 1000000000
using namespace std;
int n, A[NMAX][NMAX], B[NMAX][NMAX], source, dest, res, sol[NMAX], r;
int D1[NMAX], D2[NMAX];
char use, type, x, y;
queue <int> Q;
bool in[NMAX];

void fill(int A[NMAX][NMAX])
{
int i, j;
for (i = 0; i < NMAX; i++)
for (j = 0; j < NMAX; j++)
A[i][j] = INF;

for (i = 0; i < NMAX; i++)
A[i][i] = 0;
}

void update(int val, int pos)
{
if (val == res)
sol[++r] = pos;
if (val < res)
res = val, sol[r = 1] = pos;
}

void bford(int start, int D[NMAX], int cost[NMAX][NMAX])
{
int i, node;
for (i = 0; i < NMAX; i++)
D[i] = INF;
D[start] = 0;
Q.push(start); in[start] = true;

while (!Q.empty())
{
node = Q.front();
Q.pop(); in[node] = false;
for (i = 0; i < NMAX; i++)
if (cost[node][i] != INF && D[i] > D[node] + cost[node][i])
{
D[i] = D[node] + cost[node][i];
if (!in[i])
Q.push(i), in[i] = true;
}
}
}

int main()
{
//freopen("input", "r", stdin);
int i, cost, test_no = 0;
while (scanf("%d\n", &n), n)
{
test_no++;

fill(A), fill(B);
for (i = 1; i <= n; i++)
{
scanf("%c %c %c %c %d\n", &use, &type, &x, &y, &cost);
if (use == 'Y')
{
A[x - 'A'][y - 'A'] = min(A[x - 'A'][y - 'A'], cost);
if (type == 'B')
A[y - 'A'][x - 'A'] = min(A[y - 'A'][x - 'A'], cost);
}
else
{
B[x - 'A'][y - 'A'] = min(B[x - 'A'][y - 'A'], cost);
if (type == 'B')
B[y - 'A'][x - 'A'] = min(B[y - 'A'][x - 'A'], cost);
}
}
scanf("%c %c\n", &x, &y);
source = x - 'A'; dest = y - 'A';

bford(source, D1, A);
bford(dest, D2, B);

r = 0; res = INF;
for (i = 0; i < NMAX; i++)
update(D1[i] + D2[i], i);

if (res == INF)
printf("You will never meet.");
else
{
printf("%d ", res);
for (i = 1; i < r; i++)
printf("%c ", sol[i] + 'A');
printf("%c", sol[r] + 'A');
}
printf("\n");
}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10171 - Meeting Prof. Miguel

From uhunt:
Siegrift> cosmin79: I am not sure if the bford method is correct, try dijkstra
Siegrift> in my ACC i used dijkstra with priority queue
Check input and AC output for thousands of problems on uDebug!

cosmin79
New poster
Posts: 11
Joined: Fri Aug 09, 2013 7:25 pm

### Re: 10171 - Meeting Prof. Miguel

I highly doubt it's the bford. I've tried to code the SSSP part using roy-floyd, bford and now dijkstra as you've suggested (just to be on the safe side). The verdict is still WA. The new code:

Code: Select all

``````#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <queue>
#include <vector>
#define NMAX 26
#define INF 1000000000
#define pii pair <int, int>
#define mp make_pair
#define x first
#define y second
using namespace std;
int n, A[NMAX][NMAX], B[NMAX][NMAX], source, dest, res, sol[NMAX], r;
int D1[NMAX], D2[NMAX];
char use, type, x, y;
priority_queue < pii, vector <pii>, greater <pii> > Q;

void fill(int A[NMAX][NMAX])
{
int i, j;
for (i = 0; i < NMAX; i++)
for (j = 0; j < NMAX; j++)
A[i][j] = INF;

for (i = 0; i < NMAX; i++)
A[i][i] = 0;
}

void update(int val, int pos)
{
if (val == res)
sol[++r] = pos;
if (val < res)
res = val, sol[r = 1] = pos;
}

void dijkstra(int start, int D[NMAX], int cost[NMAX][NMAX])
{
int i, node, curr_cost;
for (i = 0; i < NMAX; i++)
D[i] = INF;
D[start] = 0;
Q.push(mp(0, start));

while (!Q.empty())
{
node = Q.top().y; curr_cost = Q.top().x;
Q.pop();
if (curr_cost > D[node])
continue ;

for (i = 0; i < NMAX; i++)
if (D[i] > curr_cost + cost[node][i])
{
D[i] = curr_cost + cost[node][i];
Q.push(mp(D[i], i));
}
}
}

int main()
{
//freopen("input", "r", stdin);
int i, cost, test_no = 0;
while (scanf("%d\n", &n), n)
{
test_no++;

fill(A), fill(B);
for (i = 1; i <= n; i++)
{
scanf("%c %c %c %c %d\n", &use, &type, &x, &y, &cost);
if (use == 'Y')
{
A[x - 'A'][y - 'A'] = min(A[x - 'A'][y - 'A'], cost);
if (type == 'B')
A[y - 'A'][x - 'A'] = min(A[y - 'A'][x - 'A'], cost);
}
else
{
B[x - 'A'][y - 'A'] = min(B[x - 'A'][y - 'A'], cost);
if (type == 'B')
B[y - 'A'][x - 'A'] = min(B[y - 'A'][x - 'A'], cost);
}
}
scanf("%c %c\n", &x, &y);
source = x - 'A'; dest = y - 'A';

dijkstra(source, D1, A);
dijkstra(dest, D2, B);

r = 0; res = INF;
for (i = 0; i < NMAX; i++)
update(D1[i] + D2[i], i);

if (res == INF)
printf("You will never meet.");
else
{
printf("%d ", res);
for (i = 1; i < r; i++)
printf("%c ", sol[i] + 'A');
printf("%c", sol[r] + 'A');
}
printf("\n");
}
return 0;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10171 - Meeting Prof. Miguel

cosmin79, increase the size of sol to NMAX + 1
Check input and AC output for thousands of problems on uDebug!

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

### Re: 10171 - Meeting Prof. Miguel

Thanks a lot sir BrainFry..

Code: Select all

``//Accepted``
Last edited by raj on Sat Feb 15, 2014 12:26 am, edited 1 time in total.