メモの日々

旧バージョンから次をコピーする。
- .htaccess
- index.rdf
- mimetex.xcg
- no_comments.rdf
- tdiary.common.conf
  - 異なるパスで動作確認する際には「@options['sp.path']」に設定しているパスを変更する必要があることに注意。
- tdiary.conf
  - 異なるパスで動作確認する際には「@index」と最後のevalの行に設定しているパスを変更する必要があることに注意。
index.rbとupdate.rbをそれぞれindex.cgiとupdate.cgiという名前のファイルにコピーする。スレッドメモから参照されるので.rbの方も残しておく必要がある。
index.cgiとupdate.cgiの1行目を「#!/usr/local/bin/ruby2.6」に書き換える。このサーバにRuby 2.7は用意されていないみたい。
次のファイルに実行権限を付与する。
- index.cgi
- update.cgi
- mimetex.xcg

プラグイン

旧バージョンの misc/plugin/ から次をコピーする。
- jdate.rb
- mathjax.rb
- mimetex.rb
- section_permalink.rb
- section_permalink_anchor.rb
- title_anchor.rb
category-legacy.rbには独自の変更をしていたが、これをしなくても新しい順に表示されるようになっていた。ただ、動作がおかしい所もあるので後で調べる。
- → コードに問題があったのでpull requestを送って取り込んでもらえた。
5.1.0リリースの説明を参考に、amazon.rbの新しい設定を行う。が、今のところ書影は表示されない。
- → amazon.rbはどうしても動くようにできなかったので、新しいプラグインopenbd.rbを作った。

[ツッコミを入れる]

2020年06月02日(火) [長年日記]

■ [dev][c++] 単一始点最短経路問題の解法

最短経路問題を解く幅優先探索とダイクストラ法をメモ。

幅優先探索

すべての辺の重みが等しいグラフに対する単一始点最短経路問題は幅優先探索で効率よく解ける。幅優先探索はキューを使って始点に近い頂点から順に経路の重みを決定していくように実装すればよい。

Aizu Online Judgeに幅優先探索の問題があるのでこれを解くC++コードをメモ。

#include <iostream>
#include <queue>
#include <vector>

struct node
{
  int name;
  std::vector<node*> neighbors;
  int distance_from_root{-1};
};

void solve(std::vector<node>& nodes)
{
  std::queue<node*> queue;
  auto& root = nodes.front();
  root.distance_from_root = 0;
  queue.push(&root);

  while (!queue.empty()) {
    auto* target = queue.front();
    queue.pop();

    for (auto* n : target->neighbors) {
      if (n->distance_from_root >= 0) continue;
      n->distance_from_root = target->distance_from_root + 1;
      queue.push(n);
    }
  }
}

int main()
{
  int n;
  std::cin >> n;

  std::vector<node> nodes(n);
  for (int i = 0; i < n; ++i) {
    int u, k;
    std::cin >> u >> k;
    auto& node = nodes.at(u - 1);
    node.name = u;
    node.neighbors.resize(k);
    for (auto& nb : node.neighbors) {
      int v;
      std::cin >> v;
      nb = &nodes.at(v - 1);
    }
  }

  solve(nodes);

  for (const auto& node : nodes) {
    std::cout << node.name << ' ' << node.distance_from_root << std::endl;
  }
}

ダイクストラ法

辺の重みが非負のグラフに対する単一始点最短経路問題にはダイクストラ法がシンプルで効率が良い。

ダイクストラ法は幅優先探索と似たコードで実装できる。キューの代わりに優先度付きキューを使い、「経路の重みの小さい頂点から辿れる頂点」から順に経路の重みを決定していくようにする。

同じくAizu Online Judgeの単一始点最短経路の問題を解くコードをメモ。

#include <iostream>
#include <limits>
#include <queue>
#include <vector>

template<typename D>
struct link
{
  D destination;
  int length;
};

struct node
{
  int name;
  std::vector<link<node*>> links;
  int distance_from_root{std::numeric_limits<int>::max()};
};

void solve(std::vector<node>& nodes, node& root)
{
  auto queue_compare = [](const node* lhs, const node* rhs) {
    return lhs->distance_from_root > rhs->distance_from_root;
  };
  std::priority_queue<
      node*,
      std::vector<node*>,
      decltype(queue_compare)
  > queue{queue_compare};

  root.distance_from_root = 0;
  queue.push(&root);

  while (!queue.empty()) {
    auto* target = queue.top();
    queue.pop();

    for (const auto& link : target->links) {
      auto* neighbor = link.destination;
      const auto d = target->distance_from_root + link.length;
      if (neighbor->distance_from_root <= d) continue;
      neighbor->distance_from_root = d;
      queue.push(neighbor);
    }
  }
}

std::string distance_string(int distance)
{
  return distance == std::numeric_limits<int>::max()
      ? "INF"
      : std::to_string(distance);
}

int main()
{
  int node_count, link_count, root_name;
  std::cin >> node_count >> link_count >> root_name;

  std::vector<node> nodes(node_count);
  for (int i = 0; i < link_count; ++i) {
    int s, t, d;
    std::cin >> s >> t >> d;
    auto& n = nodes.at(s);
    n.name = s;
    n.links.push_back(link<node*>{&nodes.at(t), d});
  }

  solve(nodes, nodes.at(root_name));

  for (const auto& n : nodes) {
    std::cout << distance_string(n.distance_from_root) << std::endl;
  }
}

[ツッコミを入れる]

トップ