#1197971

Solution for 0304: School Cafeteria by okuraofvegetable

Source Code Status Test Cases
    Policy: public     Reviewed: 191    
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 #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags