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
Why WA all time.... 
can't find specific case to get AC... please help someone.... thanks in advance.
can't find specific case to get AC... please help someone.... thanks in advance.
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
Why WA all time.... can't find specific case to get AC... please help someone.... thanks in advance.
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 :Output should be :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 0Code: 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!
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:
so can anybody find my mistake or give me a case? my email address : wangtaoboy@foxmail.com
Thank you!!!!!!
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;
}
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:AC output:
Code: Select all
1
M U A B 100
C A
0Code: Select all
You will never meet.Check input and AC output for thousands of problems on uDebug!
Re: 10171 - Meeting Prof. Miguel
Hi, I have found my mistake before this , and I hava gotten accepted.I made some mistake in initial and thaks anyway.brianfry713 wrote:Input:AC output:Code: Select all
1 M U A B 100 C A 0Code: Select all
You will never meet.
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;
}
}
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:AC output:
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
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!
Re: 10171 - Meeting Prof. Miguel
Thanks brianfry713! I got AC. 
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
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!
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!
Re: 10171 - Meeting Prof. Miguel
Last edited by raj on Sat Feb 15, 2014 12:26 am, edited 1 time in total.