読者です 読者をやめる 読者になる 読者になる

SPOJ: EZDIJKST

問題

www.spoj.com

解説

ダイクストラライブラリ確認用

コード

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iterator>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)

typedef long long ll;

template <typename T>
class Dijkstra {
 public:
  Dijkstra(int vertex_num) {
    this->vertex_num = vertex_num;
    edges = vector<vector<tuple<int, T>>>(vertex_num);
    distances = vector<T>(vertex_num);
  }

  void addEdge(int from, int dest, T cost) {
    edges[from].push_back(make_tuple(dest, cost));
  }

  void update(int source) {
    for (int i = 0; i < vertex_num; ++i) distances[i] = -1;
    distances[source] = 0;
    priority_queue<tuple<T, int>, vector<tuple<T, int>>, greater<tuple<T, int>>>
        q;
    q.push(make_tuple(0, source));
    while (!q.empty()) {
      int vertex = get<1>(q.top());
      T distance = get<0>(q.top());
      q.pop();
      if (distances[vertex] < distance) continue;
      for (auto e : edges[vertex]) {
        int next_vertex = get<0>(e);
        T next_distance = get<1>(e) + distance;
        if (distances[next_vertex] == -1 ||
            next_distance < distances[next_vertex]) {
          distances[next_vertex] = next_distance;
          q.push(make_tuple(next_distance, next_vertex));
        }
      }
    }
  }

  T getDistance(int vertex) { return distances[vertex]; }

 private:
  int vertex_num;
  vector<vector<tuple<int, T>>> edges;
  vector<T> distances;
  Dijkstra() {}
};

void solve() {
  int V, K;
  cin >> V >> K;
  Dijkstra<int> dijkstra(V);
  for (int i = 0; i < K; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    a--,b--;
    dijkstra.addEdge(a, b, c);
  }
  int start, goal;
  cin >> start >> goal;
  start--, goal--;
  dijkstra.update(start);
  if (dijkstra.getDistance(goal) >= 0) {
    cout << dijkstra.getDistance(goal) << endl;
  } else {
    puts("NO");
  }
}

int main() {
  int t;
  cin >> t;
  for (int i = 0; i < t; ++i) {
    solve();
  }
}