SPOJ: EZDIJKST
問題
解説
ダイクストラライブラリ確認用
コード
#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(); } }