UVA/10171.cpp at master · johan-smc/UVA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>


using namespace std;
#define INF 1<<27

int n;

void floyd( int arr[ 27 ][ 27 ] )
{
  for( int k = 0 ; k < 26 ; ++k )
    for( int i = 0 ; i < 26 ; ++i )
      for( int j = 0 ; j < 26 ; ++j )
        arr[ i ][ j ] = min ( arr [ i ][ j ] , arr[ i ][ k ] + arr[ k ][ j ] );
}

int main()
{
  int graphI[ 27 ][ 27 ];
  int graphMiguel[ 27 ][ 27 ];
  while( scanf("%d",&n ), n )
  {
    for( int i = 0 ; i < 27 ; ++i )
      for( int j = 0 ; j < 27 ; ++j )
      {
        graphI[ i ][ j ] = i==j?0:INF;
        graphMiguel[ i ][ j ] = i==j?0:INF;
      }
    char p,d,ini,fin;
    int val;
    for( int i = 0 ; i < n ; ++i )
    {
      scanf(" %c %c %c %c %d",&p,&d,&ini,&fin,&val );
      if( p == 'Y')
      {
          graphI[ ini-'A' ][ fin-'A' ] =  min (graphI[ ini-'A' ][ fin-'A' ],val);
          if( d == 'B' )
            graphI[ fin-'A' ][ ini-'A' ] =  min (graphI[ fin-'A' ][ ini-'A' ],val);

      }
      else
      {
          graphMiguel[ ini-'A' ][ fin-'A' ] = min (graphMiguel[ ini-'A' ][ fin-'A' ],val);
          if( d == 'B' )
            graphMiguel[ fin-'A' ][ ini-'A' ] = min (graphMiguel[ fin-'A' ][ ini-'A' ],val);

      }
      // cout << "estue " << endl;
    }
    // cout << "jaja " << endl;
    scanf(" %c %c",&ini,&fin );
    // cout << "ley" << endl;
    floyd( graphI );
    floyd( graphMiguel );
    int men=INF;
    queue< char > pasos;
    for( int j = 0 ; j < 26 ; ++j )
    {
      int menI, menMiguel;
      menI = menMiguel = INF;
      menI =  graphI[ ini-'A' ][ j ] ;
      menMiguel =  graphMiguel[ fin-'A' ][ j ];
      if( menI != INF && menMiguel != INF )
      {
        if( men > menI + menMiguel )
        {
          men = menI + menMiguel;
          while( !pasos.empty() ) pasos.pop();
          pasos.push( 'A'+j );
        }
        else if( men == menI + menMiguel )
          pasos.push( 'A'+j );
      }
    }
    if( men == INF )
      printf("You will never meet." );
    else
    {
      printf("%d ",men );
      while( !pasos.empty() )
      {
        printf("%c",pasos.front() );
        pasos.pop();
        if( !pasos.empty() )
          printf(" ");
      }
    }
    printf("\n" );
  }
  return 0;
}