#include #include #include using namespace std; // +oo #define INFTY 99999999 // Bunch of macros to save some writing. #define ii pair #define vi vector #define vii vector #define vvi vector #define vvii vector // Operator used for comparison within the priority queue // holding pair values representing a node and // its distance from the start node. class cmpii { public: // The call operator needs to be overloaded in order // to customize priority_queue. Return true, if x // has lower priority than y. bool operator()(const ii& x, const ii& y) { return x.second > y.second; } }; // Dijkstra's shortest path algorithm. void dijkstra(vvii &G, vi &distances, int S, int D) { // Indicator of nodes which shortest path // distances were determined. // XXX: Do we need such an indicator array? vector found(G.size(), false); // Upper bounds on distances from starting // node S for all nodes. distances.resize(G.size()); // Initialize the distances. fill(distances.begin(), distances.end(), INFTY); // We definitely know this :). distances[S] = 0; // Priority queue holding the estimates of // the shortest paths from node S to every // (so far) visited node. priority_queue Q; // Push the start node S into the queue. Q.push(ii(S, distances[S])); while (!Q.empty()) { int u = Q.top().first; Q.pop(); // Continue if we already found the shortest // path for this node. // XXX: Why we might use something like this? // Is it necessary? if (found[u]) continue; found[u] = true; // Did we found the shortest path to // the destination node D? if (u == D) break; // Relax (re-estimate) the shortest paths to all // neighboring nodes of node u. for (vii::iterator e = G[u].begin(); e != G[u].end(); ++e) { // Trying an edge e = (u, v) with length w. int v = e->first; int w = e->second; // Check whether we can get to node v through // node u using shorter distance than what is // the current estimate for u. if (!found[v] && distances[v] > distances[u] + w) { distances[v] = distances[u] + w; Q.push(ii(v, distances[v])); } } } } int main(void) { int A, B, T, V, K, a, b, c; // Make cout and cin faster if you prefer // them over their C alternatives. ios::sync_with_stdio(false); cin >> T; while (T--) { // Read the graph size. cin >> V >> K; // Adjacency list representation // of the graph. vvii G(V); // Read the graph specification. for (int i = 0; i < K; ++i) { cin >> a >> b >> c; // Add edge from a to b. G[a - 1].push_back(ii(b - 1, c)); } // Read the starting and destination node. cin >> A >> B; --A; --B; // (Upper-bounds on) distances to all nodes // from starting node A. vi distances; dijkstra(G, distances, A, B); // If we found a shortest path to the destination node B, // print its length, otherwise, print 'NO'. if (distances[B] != INFTY) cout << distances[B] << endl; else cout << "NO" << endl; } return 0; }