Page 4 of 5

Re: 10171 - Meeting Prof. Miguel

Posted: Fri Oct 19, 2012 10:05 pm
by brianfry713
Try the I/O in the post before yours.

Re: 10171 - Meeting Prof. Miguel

Posted: Sat Oct 20, 2012 4:59 am
by Raihan_SUST
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]

Re: 10171 - Meeting Prof. Miguel

Posted: Sat Oct 20, 2012 5:06 am
by Raihan_SUST
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);
    }
}

Re: 10171 - Meeting Prof. Miguel

Posted: Tue Oct 23, 2012 11:04 pm
by brianfry713
@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

Re: 10171 - Meeting Prof. Miguel

Posted: Fri Dec 07, 2012 4:28 pm
by boy wang
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!!!!!!

Re: 10171 - Meeting Prof. Miguel

Posted: Wed Dec 12, 2012 12:38 am
by brianfry713
Input:

Code: Select all

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

Code: Select all

You will never meet.

Re: 10171 - Meeting Prof. Miguel

Posted: Sat Dec 15, 2012 7:01 pm
by boy wang
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;
}
}

Re: 10171 - Meeting Prof. Miguel

Posted: Sat Aug 24, 2013 2:57 am
by elexhobby
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;
}

Re: 10171 - Meeting Prof. Miguel

Posted: Tue Aug 27, 2013 11:12 pm
by brianfry713
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.

Re: 10171 - Meeting Prof. Miguel

Posted: Sat Aug 31, 2013 10:38 pm
by elexhobby
Thanks brianfry713! I got AC. :)

Re: 10171 - Meeting Prof. Miguel

Posted: Fri Sep 20, 2013 1:45 pm
by cosmin79
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;
}

Re: 10171 - Meeting Prof. Miguel

Posted: Fri Sep 20, 2013 9:27 pm
by brianfry713
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

Re: 10171 - Meeting Prof. Miguel

Posted: Fri Sep 20, 2013 9:45 pm
by cosmin79
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;
}


Re: 10171 - Meeting Prof. Miguel

Posted: Fri Sep 20, 2013 10:36 pm
by brianfry713
cosmin79, increase the size of sol to NMAX + 1

Re: 10171 - Meeting Prof. Miguel

Posted: Fri Feb 14, 2014 8:53 pm
by raj
Thanks a lot sir BrainFry.. :) :)

Code: Select all

//Accepted