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()
- {
-
-
- 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();
- }
- }
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.