Tuenti Contest 12 (Pablo Moreno)

/*
    Author: Pablo Moreno Olalla
    Email address: darthbrevu@yahoo.es
*/
#include <list>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <sstream>
#include <iostream>
#include <algorithm>

using namespace std;

string baz="BAZINGA";

inline void tokenize(const string &in,list<string> &out)    {
    int pos1=0,pos2;
    for (;;)    {
        pos1=in.find_first_not_of(' ',pos1);
        if (pos1==string::npos) return;
        pos2=in.find_first_of(' ',pos1);
        if (pos2==string::npos) {
            out.push_back(in.substr(pos1));
            return;
        }   else out.push_back(in.substr(pos1,pos2-pos1));
        pos1=pos2;
    }
}

class DGraph    {
public:
    class Entry {
    public:
        unsigned int o;
        unsigned int d;
        int w;
    };
    unsigned int size;
    unsigned int o;
    unsigned int d;
    list<Entry> sparseData;
private:
    struct Edge {
    public:
        bool exists;
        int w;
        inline Edge():exists(false) {}
    };
    void dynStep(const vector<int> *p1,vector<int> *p2,const vector<vector<Edge> > &m) const    {
        for (size_t i=0;i<size;++i) {
            int &minV=(*p2)[i];
            minV=(*p1)[i];
            for (size_t j=0;j<size;++j) if (i!=j) if (m[j][i].exists&&((*p1)[j]<INT_MAX)) minV=min<int>(minV,m[j][i].w+(*p1)[j]);
        }
    }
    bool dynS(int &time) const  {
        vector<vector<Edge> > m(size,vector<Edge>(size));
        for (list<Entry>::const_iterator it=sparseData.begin();it!=sparseData.end();++it)   {
            Edge &e=m[it->o][it->d];
            e.exists=true;
            e.w=it->w;
        }
        vector<int> d1(size,INT_MAX),d2(size,INT_MAX);
        vector<int> *p1=&d1,*p2=&d2;
        //First step
        for (size_t i=0;i<size;++i) if (i==o) (*p1)[i]=0;
        else if (m[o][i].exists) (*p1)[i]=m[o][i].w;
        for (size_t i=1;i<size-1;++i)   {
            dynStep(p1,p2,m);   //Update p2 from p1, using m.
            swap(p1,p2);
        }
        time=(*p1)[d];
        for (size_t i=0;i<size-1;++i)   {
            dynStep(p1,p2,m);
            swap(p1,p2);
        }
        if (time>(*p1)[d]) return false;    //Negative cycle(s).
        else return time<INT_MAX;
    }
public:
    inline bool solve(int &time)    {
        int tmp;
        if (!dynS(tmp)) return false;
        time+=tmp;
        return true;
    }
};

int main(int argc,char **argv)  {
    //The first two lines are not strictly necessary, but make the code a little more handy.
    if (argc>=2) freopen(argv[1],"r",stdin);
    if (argc>=3) freopen(argv[2],"w",stdout);
    string tmp;
    DGraph::Entry ge;
    int res;
    list<string> toks;
    for (;;)    {
        getline(cin,tmp);
        DGraph prob;
        tokenize(tmp,toks);
        if (toks.size()<3) break;
        list<string>::const_iterator it=toks.begin();
        if (sscanf(it->c_str(),"%u",&prob.size)!=1) break;
        ++it;
        if (sscanf(it->c_str(),"%u",&prob.o)!=1) break;
        ++it;
        if (sscanf(it->c_str(),"%u",&prob.d)!=1) break;
        ++it;
        ge.w=0;
        for (;it!=toks.end();++it)  {
            if (sscanf(it->c_str(),"%u,%u,%d",&ge.o,&ge.d,&ge.w)!=3) break;
            else if ((ge.o<prob.size)&&ge.d<prob.size) prob.sparseData.push_back(ge);
        }
        toks.clear();
        res=25000;
        if (prob.solve(res)) cout<<res<<endl;
        else cout<<baz<<endl;
    }
    return 0;
}