Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на C++:

#include < vector >
#include < iostream >
#include < iomanip >
#include < string >
using namespace std;
const int MAXN = 30;
const int MAXDIST = 100000000;
int distanc[MAXN][MAXN];
 
int dist[MAXN][MAXN];
 
int next[MAXN][MAXN];
 
string name[MAXN];
//all the Cs that the shortest path from A to C will pass B.
vector < int > passby[MAXN][MAXN];

void ShowMatrix(int matrix[MAXN][MAXN], int rows, int cols)
{
    int i, j;
    for ( i = 0; i < rows; i ++ )
    {
        for ( j = 0; j < cols; j ++ )
            cout << setw(11) <<  matrix[i][j] << " ";
        cout << endl << endl << endl;
    }
    cout << " ------------------------ " << endl;
}
 
void FindPath(int a, int b)
{
    while ( a != b )
    {
        cout << a << "->" ;
        a = next[a][b];
    }
    cout << b << endl;
}

void sortD(vector<int> &verc, int a, int b, int dis)
{
    int i, j, di, dj, t;
    for ( i = 0; i < verc.size(); i ++)
    {      
        for ( j = i + 1; j < verc.size(); j ++)
        {          
            di = ( dist[a][verc[i]] - dis + 50 ) / 100;
            dj = ( dist[a][verc[j]] - dis + 50 ) / 100;
            if ( di > dj || di == dj && name[verc[i]]  > name[verc[j]])
            {
                t = verc[i];
                verc[i] = verc[j];
                verc[j] = t;
            }
        }
    }
}

int main()
{
    int n,/*Number of intersections*/
        m,/*Number of roads*/
        k,/*Number of cities*/
        s,/*Number of Signs*/
        a, b, dis, i, j;
    float d;
    cin >> n >> m >> k;
    for ( a = 0; a < n; a ++ )
        for ( b = 0; b < n ; b ++ )
            dist[a][b] = distanc[a][b] = MAXDIST;  
    for ( a = 0; a < n; a++)
        dist[a][a] = distanc[a][a] = 0;
   
    for ( i = 0; i < m; i ++ )
    {
        cin >> a >> b >> d;
        dis = (int) (d * 100 + 0.5f); 
        distanc[a][b] = distanc[b][a]
            = dist[a][b] = dist[b][a] = dis;
    }
 
    for ( i = 0; i < k; i ++ )
    {
        cin >> a;
        cin >> name[a];
    }
 
    
    for ( a = 0; a < n; a ++ )
        for ( b = 0; b < n; b ++ )
            if ( dist[a][b] < MAXDIST )
                next[a][b] = b;
    //Dijstra's algorithm.
    for ( s = 0; s < n; s ++ )
        for ( a = 0; a < n; a ++ )
            if ( dist[a][s] < MAXDIST )
               for ( b = 0; b < n; b ++ )
                   if ( dist[a][b] > dist [a][s] + dist[s][b] )
                   {
                       dist[a][b] = dist[a][s] + dist[s][b];
                   }
    
    for ( a = 0; a < n; a ++ )
        for ( b = 0; b < n; b ++)
            if ( a != b)
                for ( s = 0; s < n; s ++)
                    if ( s != a && s != b &&  distanc[a][s] < MAXDIST
                        && dist[a][b] == dist[a][s] + dist[s][b] )
                    {
                        next[a][b] = s;
                        break;
                    }
   
    for ( a = 0; a < n; a ++ )
        for ( b = 0; b < n; b ++ )
            if ( a != b )
            {
                passby[a][next[a][b]].push_back(b);
            }
   
    cin >> s;
    for ( i = 0 ; i < s ; i ++ )
    {
        cin >> a >> b >> d;
        dis = (int) ( d * 100 + 0.5f );
        sortD( passby[a][b], a, b, dis );
        for (j = 0; j < passby[a][b].size(); j++)
        {
            k = passby[a][b][j];
            if ( name[k] != "" )
                cout << setw(20) << setiosflags(ios_base::left) << name[k]
                     << ( dist[a][k] - dis + 50 ) / 100 << endl;           
        }
        cout << endl;
    }
    return 0;
}