Submission #46984895

---

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using int64 = long long;
using uint = unsigned int;
using uint64 = unsigned long long;
bool ckmin(auto& a, auto b) { return b < a ? a = b, 1 : 0; }
bool ckmax(auto& a, auto b) { return b > a ? a = b, 1 : 0; }
using namespace std;

template <typename Graph, typename F>
auto Dijkstra(Graph& g, int s, F f) {
  assert(g.IsDirected());
  using dist_t = std::invoke_result_t<F, typename Graph::edge_t&>;
  std::vector<dist_t> dist(g.n, std::numeric_limits<dist_t>::max());
  std::vector<int> from(g.n, -1);
  std::vector<bool> visit(g.n);
  dist[s] = 0;
  auto Cmp = [&](auto& p, auto& q) { return p.second > q.second; };
  std::priority_queue<std::pair<int, dist_t>,
                      std::vector<std::pair<int, dist_t>>, decltype(Cmp)>
      q(Cmp);
  q.push({s, 0});
  while (!q.empty()) {
    auto [u, du] = q.top();
    q.pop();
    if (visit[u]) continue;
    visit[u] = true;
    for (auto eid : g.go[u]) {
      auto& e = g.edges[eid];
      int v = e.v;
      if (visit[v]) continue;
      dist_t d = dist[u] + f(e);
      if (d < dist[v]) {
        dist[v] = d;
        from[v] = u;
        q.push({v, d});
      }
    }
  }
  return std::make_tuple(dist, from, visit);
}

struct EdgeBase {
  int u, v;
  operator std::string() {
    return "Edge(" + std::to_string(u) + ", " + std::to_string(v) + ")";
  }
};

template <typename Graph>
struct GraphNeighborsRange {
  struct Iterator {
    Graph* g;
    int u, id;
    bool is_directed;
    Iterator(Graph* g_, int u_, int id_) : g(g_), u(u_), id(id_) {
      is_directed = g->IsDirected();
    }
    Iterator& operator++() {
      id++;
      return *this;
    }
    bool operator!=(const Iterator& other) { return id != other.id; }
    int operator*() {
      assert(id < (int)g->go[u].size());
      auto& e = g->edges[g->go[u][id]];
      if (is_directed) {
        return e.v;
      } else {
        return u ^ e.u ^ e.v;
      }
    }
  };
  Graph* g;
  int u;
  GraphNeighborsRange(Graph* g_, int u_) : g(g_), u(u_) {
    assert(0 <= u && u < g->n);
  }
  Iterator begin() { return Iterator(g, u, 0); }
  Iterator end() { return Iterator(g, u, g->go[u].size()); }
};

template <typename Graph>
struct GraphEdgesRange {
  struct Iterator {
    Graph* g;
    int u, id;
    Iterator(Graph* g_, int u_, int id_) : g(g_), u(u_), id(id_) {}
    Iterator& operator++() {
      id++;
      return *this;
    }
    bool operator!=(const Iterator& other) { return id != other.id; }
    typename Graph::edge_t& operator*() {
      assert(id < (int)g->go[u].size());
      return g->edges[g->go[u][id]];
    }
  };
  Graph* g;
  int u;
  GraphEdgesRange(Graph* g_, int u_) : g(g_), u(u_) {
    assert(0 <= u && u < g->n);
  }
  Iterator begin() { return Iterator(g, u, 0); }
  Iterator end() { return Iterator(g, u, g->go[u].size()); }
};

template <typename Edge>
struct Graph {
  using edge_t = Edge;
  int n;
  std::vector<Edge> edges;
  std::vector<std::vector<int>> go;
  Graph(int n_) : n(n_) { go.resize(n); }
  virtual bool IsDirected() const { assert(0); }
  virtual void AddEdge(Edge e) = 0;
  GraphNeighborsRange<Graph> Neighbors(int u) {
    return GraphNeighborsRange<Graph>(this, u);
  }
  GraphEdgesRange<Graph> Edges(int u) {
    return GraphEdgesRange<Graph>(this, u);
  }
};

template <typename Edge>
struct UndirectedGraph : public Graph<Edge> {
  UndirectedGraph(int n_) : Graph<Edge>(n_) {}
  virtual bool IsDirected() const { return false; }
  virtual void AddEdge(Edge e) {
    assert(e.u >= 0 && e.u < this->n && e.v >= 0 && e.v < this->n);
    this->edges.push_back(e);
    this->go[e.u].push_back(this->edges.size() - 1);
    this->go[e.v].push_back(this->edges.size() - 1);
  }
};

template <typename Edge>
struct DirectedGraph : public Graph<Edge> {
  DirectedGraph(int n_) : Graph<Edge>(n_) {}
  virtual bool IsDirected() const { return true; }
  virtual void AddEdge(Edge e) {
    assert(e.u >= 0 && e.u < this->n && e.v >= 0 && e.v < this->n);
    this->edges.push_back(e);
    this->go[e.u].push_back(this->edges.size() - 1);
  }
};

template <typename Edge>
struct FlowGraph : public DirectedGraph<Edge> {
  using flow_t = decltype(std::declval<Edge>().cap);
  FlowGraph(int n_) : DirectedGraph<Edge>(n_) {}
  static const flow_t eps = (flow_t)1e-7;
  virtual void AddEdge(Edge) { assert(false); }
  void AddFlowEdge(Edge e) {
    DirectedGraph<Edge>::AddEdge(e);
    std::swap(e.u, e.v);
    e.cap = 0;
    DirectedGraph<Edge>::AddEdge(e);
  }
  void AddFlowEdgeWithCost(Edge e) {
    DirectedGraph<Edge>::AddEdge(e);
    std::swap(e.u, e.v);
    e.cap = 0;
    e.cost *= -1;
    DirectedGraph<Edge>::AddEdge(e);
  }
};

struct Edge {
  int u, v;
  int64 w;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  int64 A, B, C;
  cin >> n >> A >> B >> C;
  vector D(n, vector<int64>(n));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) cin >> D[i][j];
  }

  DirectedGraph<Edge> graph(2 * n);
  for (int i = 0; i < n; i++) {
    graph.AddEdge({i, i + n, 0});
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      graph.AddEdge({i, j, D[i][j] * A});
      graph.AddEdge({i + n, j + n, D[i][j] * B + C});
    }
  }

  auto [dist, from, visit] = Dijkstra(graph, 0, [](auto& e) { return e.w; });
  int64 ans = min(dist[n - 1], dist[n - 1 + n]);
  cout << ans << '\n';

  return 0;
}

Submission Info

Judge Result