Submission #221420

#	Time	Username	Problem	Language	Result	Execution time	Memory
221420		rama_pang	Wild Boar (JOI18_wild_boar)	C++14	62 / 100	15036 ms	409988 KiB

wild_boar

#include <bits/stdc++.h>
using namespace std;
using lint = long long;

const int MAXN = 2005;
const int MAXM = 4005;
const int MAXL = 100005;
const lint INF = 1e18;

struct edge_t {
  int u, v, w; // u = from, v = to, w = weight
  edge_t() {}
  edge_t(int u, int v, int w) : u(u), v(v), w(w) {}
};

int N, M, T, L;

namespace ShortestPath {

vector<edge_t> edges;
vector<int> adj[MAXN];

// Distance[X][Y][Use Y?] = Shortest Path from edges[X].u to edges[Y].v given we must use X and we must use/not use Y
lint Distance[MAXM][MAXM][2];
int LastEdgeDistance[MAXM][MAXM][2]; // last edge used in Distance[][][]

// ShortestPathEdge[X][edges[Y].v] = Y that has the shortest distance given that we have to use edge X to reach edges[Y].v
int ShortestPathEdge[MAXM][MAXN]; 

void Read() {
  M = M * 2;
  for (int i = 0; i < (M / 2); i++) {
    int A, B, C;
    cin >> A >> B >> C;
    A--, B--;

    adj[A].emplace_back(edges.size());
    edges.emplace_back(A, B, C);

    adj[B].emplace_back(edges.size());
    edges.emplace_back(B, A, C);
  }
}

void Dijkstra(int X) { // Finds all Distance[X][][1][1]
  priority_queue<pair<lint, int>, vector<pair<lint, int>>, greater<pair<lint, int>>> pq;
  pq.emplace(edges[X].w, X);
  Distance[X][X][1] = edges[X].w; // from edges[X].u to edges[X].v

  // Run Dijkstra to find Distance[X][][1][1].
  // Make sure we do not do a U-turn.

  while (!pq.empty()) {
    int cur = pq.top().second;
    lint cur_dist = pq.top().first; 
    pq.pop();

    if (cur_dist != Distance[X][cur][1]) continue;
    int u = edges[cur].v;

    for (auto nxt : adj[u]) {
      if (cur == (nxt ^ 1)) continue; // We cannot U-turn back
      lint &nxt_dist = Distance[X][nxt][1];

      if (nxt_dist == -1 || nxt_dist > cur_dist + edges[nxt].w) {
        nxt_dist = cur_dist + edges[nxt].w;
        pq.emplace(nxt_dist, nxt);
      }
    }
  }
}

void Solve() { // Computes Distance[][][][] and ShortestPathEdge[][][]
  memset(Distance, -1, sizeof(Distance));
  memset(LastEdgeDistance, -1, sizeof(LastEdgeDistance));
  memset(ShortestPathEdge, -1, sizeof(ShortestPathEdge));

  // Computes Distance[][][1] and ShortestPathEdge[][]
  for (int X = 0; X < M; X++) {
    Dijkstra(X);
    for (int Y = 0; Y < M; Y++) {
      if (Distance[X][Y][1] == -1) continue;
      LastEdgeDistance[X][Y][1] = Y;
      int V = edges[Y].v;
      int &SPE = ShortestPathEdge[X][V];
      if (SPE == -1 || Distance[X][SPE][1] > Distance[X][Y][1]) {
        SPE = Y;
      }
    }
  }

  // Computes Distance[][][0]
  for (int X = 0; X < M; X++) {
    vector<multiset<pair<lint, int>>> VertexDist(N);
    for (int Y = 0; Y < M; Y++) {
      if (Distance[X][Y][1] == -1) continue;
      VertexDist[edges[Y].v].emplace(Distance[X][Y][1], LastEdgeDistance[X][Y][1]);
    }
    for (int Y = 0; Y < M; Y++) {
      if (Distance[X][Y][1] == -1) continue;
      int V = edges[Y].v;
      auto it = VertexDist[V].find({Distance[X][Y][1], LastEdgeDistance[X][Y][1]});
      VertexDist[V].erase(it);
      if (!VertexDist[V].empty()) {
        Distance[X][Y][0] = begin(VertexDist[V])->first;
        LastEdgeDistance[X][Y][0] = begin(VertexDist[V])->second;
      }
      VertexDist[V].emplace(Distance[X][Y][1], LastEdgeDistance[X][Y][1]);
    }
  }
}

}

namespace DynamicProgramming {

int X[MAXL];

void Read() {
  for (int i = 0; i < L; i++) {
    cin >> X[i];
    X[i]--;
  }

  // T = 1
  int P, Q;
  cin >> P >> Q;
  X[--P] = --Q;
}

lint Solve() {
  vector<lint> dp(M, INF), next_dp(M, INF);

  // Special Case for pos = 0
  for (auto i : ShortestPath::adj[X[0]]) {
    for (int j = 0; j < M; j++) {
      if (ShortestPath::edges[j].v == X[1] && ShortestPath::Distance[i][j][1] != -1) {
        dp[j] = min(dp[j], ShortestPath::Distance[i][j][1]);
      }
    }
  }

  for (int pos = 1; pos < L - 1; pos++) {
    for (int last_edge = 0; last_edge < M; last_edge++) {
      if (ShortestPath::edges[last_edge].v != X[pos]) continue;

      int nxt_edge = ShortestPath::ShortestPathEdge[last_edge][X[pos + 1]];
      if (nxt_edge == -1) continue;

      next_dp[nxt_edge] = min(next_dp[nxt_edge], 
        dp[last_edge] + ShortestPath::Distance[last_edge][nxt_edge][1] - ShortestPath::edges[last_edge].w);
      
      int exclude_nxt_edge = ShortestPath::LastEdgeDistance[last_edge][nxt_edge][0];
      if (exclude_nxt_edge == -1) continue;
      next_dp[exclude_nxt_edge] = min(next_dp[exclude_nxt_edge], 
        dp[last_edge] + ShortestPath::Distance[last_edge][exclude_nxt_edge][1] - ShortestPath::edges[last_edge].w);
    }

    dp = next_dp;
    next_dp.assign(M, INF);
  }

  lint res = *min_element(begin(dp), end(dp));
  if (res == INF) res = -1;
  return res;
}

}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> M >> T >> L;

  ShortestPath::Read();
  ShortestPath::Solve();
  
  DynamicProgramming::Read();
  cout << DynamicProgramming::Solve() << "\n";

  return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 35 / 35
• Subtask 3: 15 / 15
• Subtask 4: 0 / 38