[UVa] 515 - King

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 515 - King
Source            : UVA Online Judge
Category          : Graph Theory
Algorithm         : System of Difference Constraints
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define inf           123456789  
  
static const int maxn = 1000 + 5;  
  
struct node  
{  
       int v, w;  
       node(int v = 0, int w = 0) : v(v), w(w) {}  
};  
  
vector <node> graph[maxn];  
int n, m, k;  
  
set <int> allNode;  
  
int dist[maxn];  
bool now[maxn];  
int occ[maxn];  
  
inline bool spfa(int src, int tnode)  
{  
       for (int i = 0; i < maxn; i++)  
       {  
              dist[i] = inf;  
              now[i] = 0;  
              occ[i] = 0;  
       }  
       queue <int> PQ;  
       PQ.push(src);  
       dist[src] = 0;  
       occ[src] = 1;  
       now[src] = 1;  
       while (!PQ.empty())  
       {  
              int u = PQ.front(); PQ.pop();  
              now[u] = 0;  
              for (node it : graph[u])  
              {  
                     int v = it.v;  
                     int w = it.w;  
                     if (dist[v] > dist[u] + w)  
                     {  
                            occ[v]++;  
                            dist[v] = dist[u] + w;  
                            if (!now[v]) now[v] = 1, PQ.push(v);  
                     }  
                     if (occ[v] > tnode) return false; // found negative cycle  
              }  
       }  
       return true;  
}  
  
inline void addEdge(int u, int v, int w)  
{  
       graph[u].push_back(node(v, w));  
}  
  
int main()  
{  
       //freopen("in.txt", "r", stdin);  
       while (cin >> n)  
       {  
              if (n == 0) break;  
              cin >> m;  
              int si, ni, ki;  
              string oi;  
              for (int i = 1; i <= m; i++)  
              {  
                     cin >> si >> ni >> oi >> ki;  
                     int ain = si + ni;  
                     int ai = si - 1;  
                     allNode.insert(ain+1);  
                     allNode.insert(ai+1);  
                     if (oi == "lt") addEdge(ai+1, ain+1, ki-1);  
                     else addEdge(ain+1, ai+1, -(ki+1));  
              }  
              int src = 0;  
              for (int x : allNode) addEdge(src, x, 0);  
              int tnode = allNode.size() + 1;  
              bool negativeCycle = spfa(0, tnode);  
              if (negativeCycle == false) cout << "successful conspiracy\n";  
              else cout << "lamentable kingdom\n";  
              allNode.clear();  
              for (int i = 0; i < maxn; i++) graph[i].clear();  
       }  
}