Tamflexの貯蔵庫

やる気のない備忘録

codingame - Skynet: the Virus

Ambush
Finish the 4th test of the "Skynet: the virus" puzzle with 50 or more remaining links and get a 100% score.
(訳)
待ち伏せ
"Skynet: the virus"の4番目のテストケースを50辺以上残して完了し,100%のスコアを獲得せよ.

というAcheivementがある.
大昔にできなかったのでもう一回やってみた.
敵の地点からゴール一歩前までの距離の合計を最大化する辺を削除するというアルゴリズムで行った.
距離はwarshall-floyd法で計算した.計算コストはO(n^3)
ポイントはゴール地点を通るルートは考えないことで, これはゴール地点から外に向かう辺を無効化する,すなわち部分的に有向グラフにすることで実現できる.

#include <bits/stdc++.h>
#define INF 1 << 30
#define REP(i,n) for(int i=0;i<n;i++)

using namespace std;

typedef long long ll;

typedef vector<vector<ll> > Matrix;

void warshallFloyd(Matrix& d, int n)
{
  REP(i,n) REP(j,n) REP(k,n) // i : rel :, j : src, k : dst
    d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
}

int main()
{
  int n, l, e;
  cin >> n >> l >> e;
  Matrix d(n,vector<ll>(n,INF));
  vector<vector<bool> > a(n,vector<bool>(n,false));
  REP(i,n) d[i][i] = 0;
  REP(i,l)
  {
    int s, t; cin >> s >> t;
    d[s][t]=d[t][s]=1;
    a[s][t]=a[t][s]=true;
  }
  vector<int> es;
  vector<bool> ise(n,false);
  REP(i,e)
  {
    int s; cin >> s;
    ise[s] = true;
    es.push_back(s);
    REP(j,n)
    {
      d[s][j] = INF;
      a[s][j] = false;
    }
  }
  while(1)
  {
    int si; cin >> si;
    int x, y; bool flag = true;
    REP(i,n)if(a[si][i]&&ise[i])
    {
      x = si; y = i;
      flag = false;
      break;
    }
    if(flag)
    {
      Matrix d1(d); warshallFloyd(d1,n);
      ll m = 0; REP(u,e) REP(v,n) if(a[v][es[u]]&&d1[si][v]<INF) m+=d1[si][v]+d1[v][es[u]];
      for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(a[i][j])
      {
        int p = d[i][j];
        d[i][j]=d[j][i]=INF;
        Matrix d2(d); warshallFloyd(d2,n);
        ll tm = 0; REP(u,e) REP(v,n) if(a[v][es[u]]&&d1[si][v]<INF) tm+=d2[si][v]+d2[v][es[u]];
        if(m <= tm)
        {
          m = tm;
          x = i;
          y = j;
        }
        d[i][j]=p;
        d[j][i]=(a[j][i])?p:INF;
      }
    }
    cout << x << " " << y << endl;
    d[x][y]=d[y][x]=INF;
    a[x][y]=a[y][x]=false;
  }
}