Solution To 'The Gathering'

gather.cpp

#include <iostream>
#include <sstream>
#include <vector>
#include <map>
#include <math.h>
#include <algorithm>
#include <numeric>
#include <bitset>
#include <stack>
#include <queue>
#include <set>
#include <fstream>
#include <cassert>
#include <cstring>
using namespace std;

int dr[]={0,1,0,-1,1,1,-1,-1};
int dc[]={1,0,-1,0,1,-1,1,-1};
#define zmax(a,b) (((a)>(b))?(a):(b))
#define zmin(a,b) (((a)>(b))?(b):(a))
#define zabs(a) (((a)>=0)?(a):(-(a)))
#define iif(c,t,f) ((c)?(t):(f))
template<class A, class B> A cvt(B x) {stringstream s;s<<x;A r;s>>r;return r;}

struct edge
{
  edge(int pvert, int plen, int pcap) : vert(pvert), len(plen), cap(pcap) {}
  int vert;
  int len;
  int cap;
};

int N;
int cow[15];
vector< vector<edge> > edges;
int path[16][16][750];

int memo[1 << 15][15];
int solve(int x, int msk)
{
  int cnt = __builtin_popcount(msk) + 1;
  if(cnt == N + 1) return 0;
  
  int & ref = memo[msk][x];
  if(ref != -1) return ref;
  ref = 0x01010101;
  for(int i = 0; i < N; i++)
  {
    if(msk & 1 << i) continue;
    ref = min(ref, cnt * path[cnt][x][cow[i]] + solve(i, msk | 1 << i));
  }

  return ref;
}

int main()
{
  cin >> N;
  int P; cin >> P;
  int C; cin >> C;

  for(int i = 0; i < N; i++)
  {
    cin >> cow[i];
    cow[i]--;
  }

  edges = vector< vector<edge> > (P, vector<edge>());
  for(int i = 0; i < C; i++)
  {
    int A; cin >> A; A--;
    int B; cin >> B; B--;
    int L; cin >> L;
    int D; cin >> D;
    
    edges[A].push_back(edge(B, L, D));
    edges[B].push_back(edge(A, L, D));
  }

  memset(&path, 1, sizeof(path));
  for(int cap = 1; cap <= N; cap++)
  {
    for(int i = 0; i < P; i ++)
      for(int j = 0; j < edges[i].size(); j++)
        if(edges[i][j].cap < cap)
          edges[i].erase(edges[i].begin() + j--);
    
    for(int a = 0; a < N; a++)
    {
      priority_queue< pair<int, int > > q;
      q.push(make_pair(0, cow[a]));
      path[cap][a][cow[a]] = 0;
      while(!q.empty())
      {
        pair<int, int> pr = q.top(); q.pop();
        int v = pr.second;
        int len = -pr.first;

        if(len != path[cap][a][v]) continue;

        for(int i = 0; i < edges[v].size(); i++)
        {
          edge e = edges[v][i];
          if(len + e.len < path[cap][a][e.vert])
          {
            path[cap][a][e.vert] = len + e.len;
            q.push(make_pair(-len - e.len, e.vert));
          }
        }
      }
    }
  }

  memset(&memo, -1, sizeof(memo));
  int res = 0x01010101;
  for(int i = 0; i < N; i++)
    res = min(res, path[1][i][0] + solve(i, 1 << i));

  cout << res << endl;
  return 0;
}