Участник:Krivosheev.ah/TRSTAGE

Материал из DISCOPAL
Перейти к: навигация, поиск

C++ (gcc 8.3)

https://www.spoj.com/problems/TRSTAGE/

#include <iostream>
#include <cstdio>
#include <cstring>
 
using namespace std;
 
const int inf = (1 << 30) - 1;
int n, m, p, a, b;
int adjm[31][31];
int ticket[9];
 
double results[31][256];
double gen(int node, int bitmask)
{
    if (node == b)
    {
        return 0;
    }
    if (results[node][bitmask] != -1)
    {
        return results[node][bitmask];
    }
    results[node][bitmask] = inf;
    for (int i = 0; i < m; i++)
    {
        if (adjm[node][i] == -1) continue;
 
        for (int j = 0; j < n; j++)
        {
            if (bitmask & (1 << j)) continue;
            // cout << node << " -> " << i << "  , bitmask: " << bitmask << " -> " << int(bitmask | (1 << j)) << endl;
            int newmask = bitmask | (1 << j);
            results[node][bitmask] = std::min(results[node][bitmask], adjm[node][i] / static_cast < double > (ticket[j]) + gen(i, newmask));
        }
    }
    return results[node][bitmask];
}
int main()
{
    while (true)
    {
        scanf("%d %d %d %d %d", &n, &m, &p, &a, &b);
 
        if (n + m + p + a + b == 0)
        {
            return 0;
        }
        a--;
        b--;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &ticket[i]);
        }
        memset(adjm, -1, sizeof(adjm));
        int x, y, z;
        for (int i = 0; i < p; i++)
        {
            scanf("%d %d %d", &x, &y, &z);
            adjm[x-1][y-1] = adjm[y-1][x-1] = z;
        }
        for (int i = 0; i < m; i++)
        {
            fill(results[i], results[i] + (1 << n), -1);
        }
        double sol = gen(a, 0);
        if (sol == inf)
        {
            printf("Impossible\n");
        }
        else
        {
            printf("%lf\n", sol);
        }
    }
    return 0;
}