[POJ] 2983 Is the Information Reliable?

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 2983 Is the Information Reliable?
Source            : POJ
Category          : Graph Theory
Algorithm         : System of Difference Constraints
Verdict           : Accepted

#include "iostream"  
#include "queue"  
#include "vector"  
  
using namespace std;  
  
#define inf             123456789  
  
static const int maxn = 1000 + 5;  
  
struct info  
{  
      int v, w;  
      info(int v = 0, int w = 0) : v(v), w(w) {}  
};  
  
vector <info> graph[maxn];  
int n, m;  
int dis[maxn], now[maxn], cnt[maxn];  
  
inline void createGraph()  
{  
      for (int i = 1; i <= n; i++)  
      {  
            graph[0].push_back(info(i, 0));  
      }  
}  
  
inline bool spfa(int src = 0)  
{  
      for (int i = 0; i < maxn; i++)  
      {  
            dis[i] = inf;  
            now[i] = 0;  
            cnt[i] = 0;  
      }  
      queue <int> PQ;  
      PQ.push(src);  
      dis[src] = 0;  
      now[src] = 1;  
      cnt[src] = 1;  
      while (!PQ.empty())  
      {  
            int u = PQ.front(); PQ.pop();  
            now[u] = 0;  
            if (cnt[u] > n) return false;  
            int len = (int)graph[u].size();  
            for (int i = 0; i < len; i++)  
            {  
                  int v = graph[u][i].v;  
                  int w = graph[u][i].w;  
                  if (dis[v] > dis[u] + w)  
                  {  
                        dis[v] = dis[u] + w;  
                        cnt[v]++;  
                        if (!now[v]) now[v] = 1, PQ.push(v);  
                  }  
            }  
      }  
      return true;  
}  
  
int main()  
{  
      //freopen("in.txt", "r", stdin);  
  
      ios_base::sync_with_stdio(false);  
      cin.tie(NULL);  
  
      while (cin >> n >> m)  
      {  
            char t;  
            int u, v, x;  
            for (int e = 1; e <= m; e++)  
            {  
                  cin >> t >> u >> v;  
                  if (t == 'P')  
                  {  
                        cin >> x;  
                        graph[v].push_back(info(u, -x));  
                        graph[u].push_back(info(v, x));  
                  }  
                  else  
                  {  
                        graph[v].push_back(info(u, -1));  
                  }  
            }  
            createGraph();  
            if (spfa() == false) cout << "Unreliable\n";  
            else cout << "Reliable\n";  
            for (int i = 0; i < maxn; i++) graph[i].clear();  
      }  
}