## #1197971

Solution for 0304: School Cafeteria by okuraofvegetable

Source Code Status Test Cases
Policy: public     Reviewed: 215
00.00 sec    1300 KB    132 lines     3054 bytes    2015-01-28 07:55
```#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> T;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define EQ(a,b) (abs((a)-(b))<eps)
int N,C;
struct edge
{
int from,to,cost;
edge(int from,int to,int cost):from(from),to(to),cost(cost){}
};
vector<edge> es,both;
vector<T> other;
int K;
int D[105];
int bellmanford(int x)
{
for(int i=0;i<N;i++)D[i]=INF;
D[0]=0;
vector<int> v;
for(int i=0;i<K;i++)v.pb((x>>i)&1);
both.clear();
for(int i=0;i<K;i++)
{
int a,b,c;
a = other[i].fi.fi;
b = other[i].fi.sec;
c = other[i].sec;
if(v[i]==0)
{
both.pb(edge(b,a,0));
if(c>0)both.pb(edge(a,b,c));
else both.pb(edge(b,a,c));
}
else
{
both.pb(edge(a,b,0));
if(c>0)both.pb(edge(b,a,c));
else both.pb(edge(a,b,c));
}
}
for(int i=0;i<N;i++)
{
for(int j=0;j<es.size();j++)
{
if(D[es[j].from]<INF&&D[es[j].to]>D[es[j].from]+es[j].cost)
{
if(i==N-1)return -1;
D[es[j].to]=D[es[j].from]+es[j].cost;
}
}
for(int j=0;j<both.size();j++)
{
if(D[both[j].from]<INF&&D[both[j].to]>D[both[j].from]+both[j].cost)
{
if(i==N-1)return -1;
D[both[j].to]=D[both[j].from]+both[j].cost;
}
}
}
for(int i=0;i<N;i++)if(D[i]<0)return -1;
int ret = 0;
for(int i=0;i<N;i++)ret=max(ret,D[i]);
return ret;
}
int main()
{
scanf("%d %d",&N,&C);
for(int i=0;i<C;i++)
{
string s;
cin >> s;
stringstream ss(s);
int a,b,d;
char op,ig,sign;
ss >> a >> op;
if(op!='*')ss >> ig;
ss >> b >> sign >> d;
a--;b--;
if(op=='*')other.pb(T(P(a,b),(sign=='+'?-1:1)*d));
else
{
if(op=='<')
{
es.pb(edge(b,a,0));
if(sign=='-')es.pb(edge(a,b,d));
else es.pb(edge(b,a,-d));
}
else
{
es.pb(edge(a,b,0));
if(sign=='-')es.pb(edge(b,a,d));
else es.pb(edge(a,b,-d));
}
}
}
K = (int)other.size();
int ans = -1;
for(int i=0;i<(1<<K);i++)ans = max(ans,bellmanford(i));
if(ans==INF)printf("inf\n");
else printf("%d\n",ans);
return 0;
}

```
 Compile Error Logs: You are not authorized to see the message.

Status
 Judge: 22/22 C++ CPU: 00.00 sec Memory: 1300 KB Length: 3054 B 2015-01-28 07:55 2015-01-28 07:55
Results for testcases
 Case # Verdict CPU Time Memory In Out Case Name Case #1: : Accepted 00.00 sec 1276 KB Case #2: : Accepted 00.00 sec 1268 KB Case #3: : Accepted 00.00 sec 1248 KB Case #4: : Accepted 00.00 sec 1272 KB Case #5: : Accepted 00.00 sec 1272 KB Case #6: : Accepted 00.00 sec 1268 KB Case #7: : Accepted 00.00 sec 1272 KB Case #8: : Accepted 00.00 sec 1272 KB Case #9: : Accepted 00.00 sec 1268 KB Case #10: : Accepted 00.00 sec 1268 KB Case #11: : Accepted 00.00 sec 1292 KB Case #12: : Accepted 00.00 sec 1268 KB Case #13: : Accepted 00.00 sec 1292 KB Case #14: : Accepted 00.00 sec 1292 KB Case #15: : Accepted 00.00 sec 1292 KB Case #16: : Accepted 00.00 sec 1288 KB Case #17: : Accepted 00.00 sec 1272 KB Case #18: : Accepted 00.00 sec 1268 KB Case #19: : Accepted 00.00 sec 1272 KB Case #20: : Accepted 00.00 sec 1292 KB Case #21: : Accepted 00.00 sec 1292 KB Case #22: : Accepted 00.00 sec 1300 KB
 < prev | / | next >

 Judge Input #  ( | ) Judge Output #  ( | )