UVA Online Judge solution 515 – King – Solution in C++ – Volume 5

UVA Online Judge Solution 515 – King | Volume 5
UVA Problem Link – https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=456

Problem Name: 515 – King  solution
Problem Number : UVA – 515 – King solution
Online Judge : UVA Online Judge Solution
Volume: 5
Solution Language : C plus plus

UVA Online Judge Solution, UVA OJ Solution list, UVA Problems Solution, UVA solver, UVA all problem solution list

UVA Solution 515 – King Code in CPP:

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
struct
arc {
int
to, w;
};

arc g[105][105];
int
gt[105], inq[105], dis[105];
int
used[105];
int
neg_spfa(int n) {
static
int i, j, tn, to, w;
queue<int> Q;
for
(i = 0; i <= n; i++) {
dis[i] = 0, used[i] = 1, inq[i] = 0;
Q.push(i);
}

while
(!Q.empty()) {
tn = Q.front();
Q.pop();
used[tn] = 0;
for
(j = gt[tn]-1; j >= 0; j--) {
to = g[tn][j].to, w = g[tn][j].w;
if
(dis[to] > dis[tn] + w) {
dis[to] = dis[tn] + w;
if
(!used[to]) {
used[to] = 1;
Q.push(to);
if
(++inq[to] > n)
return
1;
}
}
}
}

return
0;
}

inline
int readchar() {
const
int N = 1048576;
static
char buf[N];
static
char *p = buf, *end = buf;
if
(p == end) {
if
((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
p = buf;
}

return
*p++;
}

inline
int ReadInt(int *x) {
static
char c, neg;
while
((c = readchar()) < '-') {if(c == EOF) return 0;}
neg = (c == '-') ? -1 : 1;
*
x = (neg == 1) ? c-'0' : 0;
while
((c = readchar()) >= '0')
*
x = (*x << 3) + (*x << 1) + c-'0';
*
x *= neg;
return
1;
}

int
main() {
int
n, m, i, j, w;
char
cmd[5];
while
(ReadInt(&n)) {
if
(n == 0) break;
ReadInt(&m);
for
(i = 0; i <= n; i++)
gt[i] = 0;
while
(m--) {
ReadInt(&i), ReadInt(&j);
cmd[0] = readchar(), cmd[1] = readchar();
ReadInt(&w);
//scanf("%d %d %s %d", &i, &j, cmd, &w);
j += i, i--; // S(j) - S(i-1)
if(cmd[0] == 'l') {// < w
w--; // <= w
g[i][gt[i]].to = j;
g[i][gt[i]++].w = w;
}
else { // > w
w++; // >= w
g[j][gt[j]].to = i;
g[j][gt[j]++].w = -w;
}
}

if
(neg_spfa(n))
puts("successful conspiracy");
else

puts("lamentable kingdom");
}

return
0;
}

Tags: UVA Online Judge Solution, UVA OJ Solution list, UVA Problems Solution, UVA solver, UVA all problem solution list, UVA code in C, UVA code in C++, UVA solution in C, UVA solution, UVA OJ problems solution, UVA solution, UVA online judge codes, UVA problem 506 solution, UVA Solution in C, UVA solution in C++, UVA  solution in java

By Maniruzzaman Akash

Maniruzzaman Akash is a freelance web developer with most popular Laravel PHP frameork and Vue JS

Leave a Reply

Your email address will not be published. Required fields are marked *