daily pastebin goal
1%
SHARE
TWEET

Tuenti Contest 12 (Pablo Moreno)

Nbrevu Jun 20th, 2011 727 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top