uva_10171(meating prof.miguel).cpp

#include<bits/stdc++.h>
using namespace std;
#define M 999999999
#define rep(i , n) for(i = 0;i < n ;i++)
#define pii make_pair

map<char, int > m ;
map<int , char>m_back ;

void warshall(int arr[][200] ,int num ){
    int i , j , k ;
    for(k =1 ; k <= num ;k++){
        for(i = 1 ;i<= num ;i++ ){
            for(j =  1;j<= num ; j++)
            {
                if(arr[i][k] + arr[k][j] <= arr[i][j]){
                    arr[i][j] = arr[i][k] + arr[k][j] ;

          }

            }
    }
}


return ;
}
vector<char  > var ;



int main(){
      freopen("in.txt","r",stdin);
   freopen("out.txt","w",stdout);
//ios_base :: sync_with_stdio(false);
//cin.tie(NULL);

char  s1[3] , s2[3] ,s3[3] ,s4[3] ;
int tc , i , j, k , des;
int arr1[200][200] , arr2[200][200] ;
    while(scanf("%d",&tc)){
      if(tc == 0) break ;
      m.clear() ;
      m_back.clear();
      rep(i , 200 ) rep(j , 200)
        arr1[i][j] =  M;

      rep(i , 200 ) rep(j , 200)
      arr2[i][j] =  M;

      int count  =1 , u ,v ;
       while(tc--){
      cin >> s1 >>s2 >>s3 >>s4 ;
      cin >>des ;
    if(s1[0] == 'Y'){
      if(m.find(s3[0] ) == m.end()){
        u = m[s3[0]] = count++;
        m_back[count-1] =  s3[0];
      }
      else
        u = m[s3[0]];

      if(m.find(s4[0] ) == m.end()) {
        v = m[s4[0]] = count++;

        m_back[count-1] =  s4[0];
      }
      else
        v = m[s4[0]];

      if(s2[0] == 'U')arr1[u][v] =  des;
      else arr1[u][v] = arr1[v][u] = des;
    }
    else{

      if(m.find(s3[0] ) == m.end()) {
        u = m[s3[0]] = count++;
        m_back[count-1] =  s3[0];
      }
     else
        u = m[s3[0]];

      if(m.find(s4[0] ) == m.end()){
        v = m[s4[0]] = count++;
        m_back[count-1] =  s4[0];
      }
      else
        v = m[s4[0]];



      if(s2[0] == 'U') arr2[u][v] =  des;
      else arr2[u][v] = arr2[v][u] = des;

    }

  }
  count-- ;
  rep(i , 200) arr1[i][i] = arr2[i][i] = 0;
  warshall(arr1 , count );
  warshall(arr2 , count );
/*
 for(i = 1; i <=count ;i++){
    for(j = 1 ;j<= count; j++)
    {
      printf("%d(%d %d) ",arr2[i][j] , i, j);

    }
printf("\n");


  }
*/

  cin >> s1 >> s2;
  u = m[s1[0]] ;
   v = m[s2[0] ];
    var.clear();
  int min ;
  min  =  M;
  vector<pair<int ,int> > _hold ;
    for(i =1 ; i<= count ;i++)
    {
      _hold.push_back(pii(arr1[u][i] + arr2[v][i],i ));
      if(arr1[u][i] + arr2[v][i] < min ){
        min = arr1[u][i] + arr2[v][i];
      }

    }
    for(i = 0 ; i< _hold.size() ; i++)
      if(_hold[i].first == min ){
        var.push_back(m_back[_hold[i].second]);

      }
sort(var.begin() , var.end() );
   if(min < M ){
    printf("%d", min);
    for(i = 0 ;i < var.size() ; i++)
      printf(" %c",var[i]);
  printf("\n");

    }
    else{
      if(s1[0] !=  s2[0])
        printf("You will never meet.\n");
      else{
        var.clear();
        var.push_back(s1[0]);
        var.push_back(s2[0]);
        sort(var.begin() , var.end());

      printf("0 %c\n",s1[0] , s2[0] ,var[0]);
      }
    }
    }


return 0 ;}