Nbrevu

Tuenti Contest 12 (Pablo Moreno)

Jun 20th, 2011
1,024
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×