前提知識

グラフの表現方法、最短経路探索アルゴリズム、幅優先探索(BFS)の理解が必要です。

第二最短経路の分類

• 一般第二経路（同一辺の重複利用可能）
• 単純第二経路（同一辺の重複利用不可）
• 厳密/非厳密第二経路（最短経路と等価/非等価）

一般第二経路

配列の最大値・次大値探索と類似した手法を用います。各頂点について最短距離と第二短距離を同時に管理します。

if (min_dist[target] > min_dist[current] + edge_weight) {
  second_dist[target] = min_dist[target];
  min_dist[target] = min_dist[current] + edge_weight;
  traversal_queue.push(target);
} else if (second_dist[target] > min_dist[current] + edge_weight) {
  second_dist[target] = min_dist[current] + edge_weight;
  traversal_queue.push(target);
}

単純第二経路

最短経路を構成する辺を順次除外し、除外後の最短経路を比較します。辺除外によって元の最短経路が使用不能となり、新たな経路が探索されます。

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

struct Point { int x, y; };
struct Connection { int destination; double cost; };

const int MAX_NODES = 210;
double primary_dist[MAX_NODES], secondary_dist[MAX_NODES];
int predecessor[MAX_NODES];
vector<Connection> graph[MAX_NODES];

double compute_distance(Point p1, Point p2) {
  double dx = p1.x - p2.x;
  double dy = p1.y - p2.y;
  return sqrt(dx*dx + dy*dy);
}

void find_shortest_path(int start) {
  fill(primary_dist, primary_dist + MAX_NODES, 1e18);
  primary_dist[start] = 0.0;
  queue<int> q;
  q.push(start);
  
  while (!q.empty()) {
    int current = q.front(); q.pop();
    for (auto conn : graph[current]) {
      int next = conn.destination;
      double cost = conn.cost;
      if (primary_dist[next] > primary_dist[current] + cost) {
        primary_dist[next] = primary_dist[current] + cost;
        predecessor[next] = current;
        q.push(next);
      }
    }
  }
}

void find_shortest_path_without_edge(int start, int u, int v) {
  fill(secondary_dist, secondary_dist + MAX_NODES, 1e18);
  secondary_dist[start] = 0.0;
  queue<int> q;
  q.push(start);
  
  while (!q.empty()) {
    int current = q.front(); q.pop();
    for (auto conn : graph[current]) {
      int next = conn.destination;
      if (current == u && next == v) continue;
      double cost = conn.cost;
      if (secondary_dist[next] > secondary_dist[current] + cost) {
        secondary_dist[next] = secondary_dist[current] + cost;
        q.push(next);
      }
    }
  }
}

int main() {
  int nodes, edges;
  cin >> nodes >> edges;
  vector<Point> points(nodes + 1);
  
  for (int i = 1; i <= nodes; i++) {
    cin >> points[i].x >> points[i].y;
  }
  
  for (int i = 0; i < edges; i++) {
    int from, to;
    cin >> from >> to;
    double cost = compute_distance(points[from], points[to]);
    graph[from].push_back({to, cost});
    graph[to].push_back({from, cost});
  }
  
  find_shortest_path(1);
  double result = 1e18;
  int current = nodes;
  
  while (predecessor[current]) {
    find_shortest_path_without_edge(1, predecessor[current], current);
    result = min(result, secondary_dist[nodes]);
    current = predecessor[current];
  }
  
  printf("%.2f\n", result);
  return 0;
}