test/verify/yosupo-shortest-path.test.cpp

• View this file on GitHub
• Last update: 2024-09-07 20:55:28+09:00
• Problem: https://judge.yosupo.jp/problem/shortest_path

Depends on

• Dijkstra(ダイクストラ法) (graph/dijkstra.hpp)
• graph/graph_template.hpp
• template/template.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/shortest_path" 

#include "template/template.hpp"
#include "graph/graph_template.hpp"
#include "graph/dijkstra.hpp"

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int N, M, s, t; cin >> N >> M >> s >> t;

  Graph<ll> gr(N);
  for(int i=0; i<M; i++) {
    ll a, b, c;
    cin >> a >> b >> c;
    gr.add_edge(a,b,c);
  }

  vector<ll>dist; vector<int>prev;

   auto pr = dijkstra_path(gr, s);
   dist = pr.first; prev = pr.second;

  if (dist[t] > LLINF) {
    cout << -1 << "\n";
  }
  else {
    ll X = dist[t];
    int Y;
    vector<int> path;
    {
      int now = t;
      while (now != -1) {
        path.push_back(now);
        now = prev[now];
      }
      Y = path.size();
    }

    reverse(path.begin(), path.end());
    cout << X << " " << Y - 1 << "\n";
    for(int i=0; i<Y-1; i++) {
      cout << path[i] << " " << path[i+1] << "\n";
    }
  }

}

#line 1 "test/verify/yosupo-shortest-path.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/shortest_path" 

#line 1 "template/template.hpp"
#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;}
const int INTINF = 1000001000;
const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const ll LLINF = 1000000000000000000;
#line 1 "graph/graph_template.hpp"



#include <vector>

template <typename T>
struct Edge {
  int from; int to;
  T cost;

  // default constructor
  Edge () : from(-1), to(-1), cost(T(0)) {}

  Edge(int _from, int _to, T _cost) : from(_from), to(_to), cost(_cost) {}

  // unweighted
  Edge(int _from, int _to) : from(_from), to(_to), cost(T(1)) {}

  bool operator==(const Edge& rhs) const {
    return from == rhs.from && to == rhs.to && cost == rhs.cost;
  }

  bool operator<(const Edge& rhs) const {
    return cost < rhs.cost;
  }
  
  bool operator>(const Edge& rhs) const {
    return cost > rhs.cost;
  }

};


template <typename T>
struct Graph : std::vector<std::vector<Edge<T>>> {

  using std::vector<std::vector<Edge<T>>>::vector; // inherit constructors

  void add_edge(int i, Edge<T> e) {
    (*this)[i].push_back(e);
  }

  void add_edge(Edge<T> e) {
    (*this)[e.from].push_back(e);
  }

  // weighted
  void add_edge(int _from, int _to, T _cost) {
    (*this)[_from].push_back(Edge(_from, _to, _cost));
  }

  // unweighted
  void add_edge(int _from, int _to) {
    (*this)[_from].push_back(Edge(_from, _to, T(1)));
  }

};


#line 1 "graph/dijkstra.hpp"



#include <queue>
#line 6 "graph/dijkstra.hpp"
#include <limits>
#include <utility>

#line 10 "graph/dijkstra.hpp"

template <typename T>
std::vector<T> dijkstra(const Graph<T>& graph, int start) {
  int N = (int)graph.size();
  constexpr T INF = numeric_limits<T>::max();
  std::vector<T>dist(N, INF);
  using P = std::pair<T, int>;

  std::priority_queue<P, std::vector<P>, std::greater<P>>que;

  que.push(make_pair(T(0), start));
  dist[start] = T(0);

  while (!que.empty()) {
    P front = que.top(); que.pop();

    if (dist[front.second] < front.first) continue;

    for (Edge ed : graph[front.second]) {

      if (dist[ed.to] > front.first + ed.cost) {
        dist[ed.to] = front.first + ed.cost;
        que.emplace(dist[ed.to], ed.to);
      }
    }
  }

  return dist;
}

template <typename T>
std::pair<std::vector<T>, std::vector<int>> dijkstra_path(const Graph<T>& graph, int start) {
  int N = (int)graph.size();
  constexpr T INF = numeric_limits<T>::max();

  using P = std::pair<T, int>;
  std::vector<T>dist(N, INF);
  std::vector<int>prev(N, -1);

  std::priority_queue<P, std::vector<P>, std::greater<P>>que;
  que.push(make_pair(T(0), start));
  dist[start] = T(0);

  while (!que.empty()) {
    P front = que.top(); que.pop();

    if (dist[front.second] < front.first) continue;

    for (Edge ed : graph[front.second]) {
      if (dist[ed.to] > front.first + ed.cost) {
        dist[ed.to] = front.first + ed.cost;
        prev[ed.to] = front.second;
        que.emplace(dist[ed.to], ed.to);
      }
    }
  }

  return make_pair(dist, prev);
}


#line 6 "test/verify/yosupo-shortest-path.test.cpp"

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int N, M, s, t; cin >> N >> M >> s >> t;

  Graph<ll> gr(N);
  for(int i=0; i<M; i++) {
    ll a, b, c;
    cin >> a >> b >> c;
    gr.add_edge(a,b,c);
  }

  vector<ll>dist; vector<int>prev;

   auto pr = dijkstra_path(gr, s);
   dist = pr.first; prev = pr.second;

  if (dist[t] > LLINF) {
    cout << -1 << "\n";
  }
  else {
    ll X = dist[t];
    int Y;
    vector<int> path;
    {
      int now = t;
      while (now != -1) {
        path.push_back(now);
        now = prev[now];
      }
      Y = path.size();
    }

    reverse(path.begin(), path.end());
    cout << X << " " << Y - 1 << "\n";
    for(int i=0; i<Y-1; i++) {
      cout << path[i] << " " << path[i+1] << "\n";
    }
  }

}

Back to top page