Cod sursa(job #637176)

Utilizator sodamngoodSo Damn Good sodamngood Data 20 noiembrie 2011 12:37:26
Problema Portal3 Scor 100
Compilator cpp Status done
Runda .com 2011 Marime 3.11 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
#define inf 2000000100
#define pii pair<long long, long long>
#define LL long long
#define x first
#define y second

int T;
LL N, M;
LL C[4], B[4];
pair<pii, pii> P[4];
vector<pair< pair<pii, pii>, LL> > V;

LL abs(LL a, LL b) {
    if(a >= b) return a-b;
    return b-a;
}

int main() {
    FILE *f1=fopen("portal3.in", "r"), *f2=fopen("portal3.out", "w");
    int i, j, p, q;

    p = 1;
    for(i=1; i<=3; i++) {
         p = 3 * p;
    }

    fscanf(f1, "%d\n", &T);
    while(T--) {
         fscanf(f1, "%lld %lld\n", &N, &M);
         //(0,0) -> (N,M)
         for(i=1; i<=3; i++) {
              fscanf(f1, "%lld %lld %lld %lld %lld\n", &P[i].x.x, &P[i].x.y, &P[i].y.x, &P[i].y.y, &C[i]);
         }

         LL sol = inf;

         for(int ki=0; ki<p; ki++) {
              q = ki;
              for(j=1; j<=3; j++) {
                   B[j] = (q % 3);
                   q = q / 3;
              }
              V.clear();
              for(j=1; j<=3; j++) {
                   if(B[j] == 1) {
                        V.push_back( make_pair( make_pair(P[j].x, P[j].y), C[j]) );
                   }
                   else if(B[j] == 2) {
                        V.push_back( make_pair( make_pair(P[j].y, P[j].x), C[j]) );
                   }
              }

              if(V.size() == 0) {
                   sol = min(sol, (LL)(N + M));

                   continue;
              }

              vector<int> perm;
              for(i=0; i<V.size(); i++) {
                   perm.push_back(i);
              }

              do {
                   LL aux = 0;
                   for(j=0; j<perm.size(); j++) {
                        //cout<<V[j].first.x.x<<" "<<V[j].first.x.y<<" -> "<<V[j].first.y.x<<" "<<V[j].first.y.y<<" , ";
                        if(j == 0 && j == perm.size()-1) {
                             aux += V[ perm[j] ].first.x.x + V[ perm[j] ].first.x.y + V[ perm[j] ].second;
                             aux += abs(N - V[ perm[j] ].first.y.x) + abs(M - V[ perm[j] ].first.y.y);
                        }
                        else if(j == 0) {
                             aux += (V[ perm[j] ].first.x.x + V[ perm[j] ].first.x.y + V[ perm[j] ].second);
                        }
                        else {
                             //(V[j-1].first.y.x, V[j-1].first.y.y) -> (V[j].first.x.x, V[j].first.x.y)
                             aux += (abs(V[ perm[j] ].first.x.x - V[ perm[j-1] ].first.y.x) + abs(V[ perm[j] ].first.x.y - V[ perm[j-1] ].first.y.y));
                             aux += V[ perm[j] ].second;

                             if(j == perm.size()-1) {
                                  aux += (abs(N - V[ perm[j] ].first.y.x) + abs(M - V[ perm[j] ].first.y.y));
                             }
                        }
                   }

                   //cout<<endl;

                   sol = min(sol, aux);

              } while(next_permutation(perm.begin(), perm.end()));
         }

         fprintf(f2, "%lld\n", sol);
    }

    fclose(f1); fclose(f2);
    return 0;
}