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

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

Re: 10171 - Meeting Prof. Miguel

Post by brianfry713 » Fri Oct 19, 2012 10:05 pm

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

Post by Raihan_SUST » Sat Oct 20, 2012 4:59 am

Why WA all time.... :cry: 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

Post by Raihan_SUST » Sat Oct 20, 2012 5:06 am

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

Post by brianfry713 » Tue Oct 23, 2012 11:04 pm

@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

Post by boy wang » Fri Dec 07, 2012 4:28 pm

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

Post by brianfry713 » Wed Dec 12, 2012 12:38 am

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

Post by boy wang » Sat Dec 15, 2012 7:01 pm

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

Post by elexhobby » Sat Aug 24, 2013 2:57 am

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

Post by brianfry713 » Tue Aug 27, 2013 11:12 pm

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

Post by elexhobby » Sat Aug 31, 2013 10:38 pm

Thanks brianfry713! I got AC. :)

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

Re: 10171 - Meeting Prof. Miguel

Post by cosmin79 » Fri Sep 20, 2013 1:45 pm

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

Post by brianfry713 » Fri Sep 20, 2013 9:27 pm

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

Post by cosmin79 » Fri Sep 20, 2013 9:45 pm

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

Post by brianfry713 » Fri Sep 20, 2013 10:36 pm

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

Post by raj » Fri Feb 14, 2014 8:53 pm

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.

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest