Nbrevu

Tuenti Contest 12 (Pablo Moreno)

Jun 20th, 2011
947
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.     Author: Pablo Moreno Olalla
  3.     Email address: darthbrevu@yahoo.es
  4. */
  5. #include <list>
  6. #include <cstdio>
  7. #include <string>
  8. #include <vector>
  9. #include <climits>
  10. #include <sstream>
  11. #include <iostream>
  12. #include <algorithm>
  13.  
  14. using namespace std;
  15.  
  16. string baz="BAZINGA";
  17.  
  18. inline void tokenize(const string &in,list<string> &out)    {
  19.     int pos1=0,pos2;
  20.     for (;;)    {
  21.         pos1=in.find_first_not_of(' ',pos1);
  22.         if (pos1==string::npos) return;
  23.         pos2=in.find_first_of(' ',pos1);
  24.         if (pos2==string::npos) {
  25.             out.push_back(in.substr(pos1));
  26.             return;
  27.         }   else out.push_back(in.substr(pos1,pos2-pos1));
  28.         pos1=pos2;
  29.     }
  30. }
  31.  
  32. class DGraph    {
  33. public:
  34.     class Entry {
  35.     public:
  36.         unsigned int o;
  37.         unsigned int d;
  38.         int w;
  39.     };
  40.     unsigned int size;
  41.     unsigned int o;
  42.     unsigned int d;
  43.     list<Entry> sparseData;
  44. private:
  45.     struct Edge {
  46.     public:
  47.         bool exists;
  48.         int w;
  49.         inline Edge():exists(false) {}
  50.     };
  51.     void dynStep(const vector<int> *p1,vector<int> *p2,const vector<vector<Edge> > &m) const    {
  52.         for (size_t i=0;i<size;++i) {
  53.             int &minV=(*p2)[i];
  54.             minV=(*p1)[i];
  55.             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]);
  56.         }
  57.     }
  58.     bool dynS(int &time) const  {
  59.         vector<vector<Edge> > m(size,vector<Edge>(size));
  60.         for (list<Entry>::const_iterator it=sparseData.begin();it!=sparseData.end();++it)   {
  61.             Edge &e=m[it->o][it->d];
  62.             e.exists=true;
  63.             e.w=it->w;
  64.         }
  65.         vector<int> d1(size,INT_MAX),d2(size,INT_MAX);
  66.         vector<int> *p1=&d1,*p2=&d2;
  67.         //First step
  68.         for (size_t i=0;i<size;++i) if (i==o) (*p1)[i]=0;
  69.         else if (m[o][i].exists) (*p1)[i]=m[o][i].w;
  70.         for (size_t i=1;i<size-1;++i)   {
  71.             dynStep(p1,p2,m);   //Update p2 from p1, using m.
  72.             swap(p1,p2);
  73.         }
  74.         time=(*p1)[d];
  75.         for (size_t i=0;i<size-1;++i)   {
  76.             dynStep(p1,p2,m);
  77.             swap(p1,p2);
  78.         }
  79.         if (time>(*p1)[d]) return false;    //Negative cycle(s).
  80.         else return time<INT_MAX;
  81.     }
  82. public:
  83.     inline bool solve(int &time)    {
  84.         int tmp;
  85.         if (!dynS(tmp)) return false;
  86.         time+=tmp;
  87.         return true;
  88.     }
  89. };
  90.  
  91. int main(int argc,char **argv)  {
  92.     //The first two lines are not strictly necessary, but make the code a little more handy.
  93.     if (argc>=2) freopen(argv[1],"r",stdin);
  94.     if (argc>=3) freopen(argv[2],"w",stdout);
  95.     string tmp;
  96.     DGraph::Entry ge;
  97.     int res;
  98.     list<string> toks;
  99.     for (;;)    {
  100.         getline(cin,tmp);
  101.         DGraph prob;
  102.         tokenize(tmp,toks);
  103.         if (toks.size()<3) break;
  104.         list<string>::const_iterator it=toks.begin();
  105.         if (sscanf(it->c_str(),"%u",&prob.size)!=1) break;
  106.         ++it;
  107.         if (sscanf(it->c_str(),"%u",&prob.o)!=1) break;
  108.         ++it;
  109.         if (sscanf(it->c_str(),"%u",&prob.d)!=1) break;
  110.         ++it;
  111.         ge.w=0;
  112.         for (;it!=toks.end();++it)  {
  113.             if (sscanf(it->c_str(),"%u,%u,%d",&ge.o,&ge.d,&ge.w)!=3) break;
  114.             else if ((ge.o<prob.size)&&ge.d<prob.size) prob.sparseData.push_back(ge);
  115.         }
  116.         toks.clear();
  117.         res=25000;
  118.         if (prob.solve(res)) cout<<res<<endl;
  119.         else cout<<baz<<endl;
  120.     }
  121.     return 0;
  122. }
RAW Paste Data