UVA

558.cpp

#include <iostream>
#include <vector>
#include <algorithm>

#define INF std::numeric_limits<int>::max()

using namespace std;

typedef struct {
  int dest, weight;
} Edge;

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

int dist[1000];

int main() {
  int t;
  cin >> t;
  for(int i=0; i < t; i++) {
    int n, m;
    cin >> n >> m;
    Graph graph(n);
    bool possible = false;

    fill(dist, dist+n, INF);
    dist[0] = 0;

    for (int j = 0; j < m; j++) {
      Edge aux;
      int src, dest, weight;
      cin >> src >> dest >> weight;
      aux.dest = dest; aux.weight = weight;
      graph[src].push_back(aux);
    }

    for(int i = 0; i < (int)graph.size() && !possible; i++) {
      for(auto edge : graph[i]) {
        if (dist[i] + edge.weight < dist[edge.dest]) {
          if (dist[edge.dest] != INF) {
            possible = true;
            break;
          }

          dist[edge.dest] = dist[i] + edge.weight;
        }
      }
    }

    if (possible) cout << "possible";
    else cout << "not possible";

    cout << endl;
  }
  return 0;
}