Cod sursa(job #1726055)

Utilizator ArmandNMArmand Nicolicioiu ArmandNM Data 7 iulie 2016 02:35:57
Problema Portal3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <fstream>
 
const int inf = 0x3f3f3f3f;
 
using namespace std;
ifstream f("portal3.in");
ofstream g("portal3.out");
 
struct Portals
{
    int X;
    int Y;
    int C;
};
 
Portals Portal[10];
int N,M,T,xd,yd,xp,yp,c;
long long TMIN;
bool used[10];
 
long long modul(long long x)
{
    if (x >= 0)
        return x;
    return -x;
}
 
void check(long long t, int x, int y)
{
    long long Tempo = 0;
    Tempo = t;
    Tempo = Tempo + modul(N - x) + modul (M - y);
    if (TMIN == 0)
        TMIN = Tempo;
    if (Tempo < TMIN)
    {
        TMIN = Tempo;
    }
}
 
void back(int k, int max, long long t, int x, int y)
{
    int p;
    if (k >= max)
    {
        check(t,x,y);
    }
    else
    {
        for (int i = 1; i <= 6; ++i)
        {
            if (!used[i])
            {
                xp = Portal[i].X;
                yp = Portal[i].Y;
                if (i % 2 == 0)
                    p = i-1;
                else
                    p = i+1;
 
                xd = Portal[p].X;
                yd = Portal[p].Y;
                c = Portal[i].C;
                int timp = 0;
                timp = timp + modul(x-xp) + modul(y-yp);
                timp += c;
                used[i] = true;
                used[p] = true;
                back(k+1,max,t+timp,xd,yd);
                used[i] = false;
                used[p] = false;
            }
        }
    }
}
 
void Solve()
{
    for (int i = 0; i <= 3; ++i)
    {
        for (int j = 1; j <= 6; ++j)
            used[j] = false;
 
        back(0,i,0,0,0);
    }
}
 
int main()
{
    f >> T;
    while (T--)
    {
        TMIN = 0;
        f >> N >> M;
        for (int i = 1; i <= 6; i+=2)
        {
            f >> Portal[i].X >> Portal[i].Y >> Portal[i+1].X >> Portal[i+1].Y >> Portal[i].C;
            Portal[i+1].C = Portal[i].C;
        }
 
        Solve();
 
        g << TMIN << '\n';
    }
 
    f.close();
    g.close();
    return 0;
}