Saturday, January 26, 2019

[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

  1. #include "iostream"  
  2. #include "queue"  
  3. #include "vector"  
  4.   
  5. using namespace std;  
  6.   
  7. #define inf             123456789  
  8.   
  9. static const int maxn = 1000 + 5;  
  10.   
  11. struct info  
  12. {  
  13.       int v, w;  
  14.       info(int v = 0, int w = 0) : v(v), w(w) {}  
  15. };  
  16.   
  17. vector <info> graph[maxn];  
  18. int n, m;  
  19. int dis[maxn], now[maxn], cnt[maxn];  
  20.   
  21. inline void createGraph()  
  22. {  
  23.       for (int i = 1; i <= n; i++)  
  24.       {  
  25.             graph[0].push_back(info(i, 0));  
  26.       }  
  27. }  
  28.   
  29. inline bool spfa(int src = 0)  
  30. {  
  31.       for (int i = 0; i < maxn; i++)  
  32.       {  
  33.             dis[i] = inf;  
  34.             now[i] = 0;  
  35.             cnt[i] = 0;  
  36.       }  
  37.       queue <int> PQ;  
  38.       PQ.push(src);  
  39.       dis[src] = 0;  
  40.       now[src] = 1;  
  41.       cnt[src] = 1;  
  42.       while (!PQ.empty())  
  43.       {  
  44.             int u = PQ.front(); PQ.pop();  
  45.             now[u] = 0;  
  46.             if (cnt[u] > n) return false;  
  47.             int len = (int)graph[u].size();  
  48.             for (int i = 0; i < len; i++)  
  49.             {  
  50.                   int v = graph[u][i].v;  
  51.                   int w = graph[u][i].w;  
  52.                   if (dis[v] > dis[u] + w)  
  53.                   {  
  54.                         dis[v] = dis[u] + w;  
  55.                         cnt[v]++;  
  56.                         if (!now[v]) now[v] = 1, PQ.push(v);  
  57.                   }  
  58.             }  
  59.       }  
  60.       return true;  
  61. }  
  62.   
  63. int main()  
  64. {  
  65.       //freopen("in.txt", "r", stdin);  
  66.   
  67.       ios_base::sync_with_stdio(false);  
  68.       cin.tie(NULL);  
  69.   
  70.       while (cin >> n >> m)  
  71.       {  
  72.             char t;  
  73.             int u, v, x;  
  74.             for (int e = 1; e <= m; e++)  
  75.             {  
  76.                   cin >> t >> u >> v;  
  77.                   if (t == 'P')  
  78.                   {  
  79.                         cin >> x;  
  80.                         graph[v].push_back(info(u, -x));  
  81.                         graph[u].push_back(info(v, x));  
  82.                   }  
  83.                   else  
  84.                   {  
  85.                         graph[v].push_back(info(u, -1));  
  86.                   }  
  87.             }  
  88.             createGraph();  
  89.             if (spfa() == false) cout << "Unreliable\n";  
  90.             else cout << "Reliable\n";  
  91.             for (int i = 0; i < maxn; i++) graph[i].clear();  
  92.       }  
  93. }  

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.