URAL1085[Meeting]

最短路,可以直接Floyd。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-4-11


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


#include <fstream>


using std::ifstream;


using std::ofstream;


#include <sstream>


using std::stringstream;


using std::endl;


#include <vector>


using std::vector;


#include <string>


using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


using std::priority_queue;


#include <set>


using std::set;


#include <map>


using std::map;


using std::pair;


using std::make_pair;


#include <algorithm>


using std::sort;


#include <cassert>


//using std::assert;


 


struct Record


{


       int money,start;


       bool have_card;


};


class Application


{


      static const int oo=1<<20;


      int N,M;


      vector<vector<int> > bus;


      int K;


      vector<Record> data;


      vector<vector<int> > cost;


      public:


      Application()


      {


                   cin>>N>>M;


                   bus.resize(M);


                   for (int i=0;i<M;i++)


                   {


                       int total;


                       cin>>total;


                       bus[i].resize(total);


                       for (int j=0;j<total;j++)


                       {


                           int get;


                           cin>>get;


                           bus[i][j]=get-1;


                       }


                   }


                   cin>>K;


                   data.resize(K);


                   for (int i=0;i<K;i++)


                   {


                       int get;


                       cin>>data[i].money>>get>>data[i].have_card;


                       data[i].start=get-1;


                   }


      }


      int run()


      {


          cost.resize(N,vector<int>(N,oo));


          for (int i=0;i<M;i++)


              for (int j=0;j<bus[i].size();j++)


                  for (int k=0;k<bus[i].size();k++)


                      cost[bus[i][j]][bus[i][k]]=1;


          for (int i=0;i<N;i++)


              cost[i][i]=0;


          for (int k=0;k<N;k++)


              for (int i=0;i<N;i++)


                  for (int j=0;j<N;j++)


                      if (cost[i][j]>cost[i][k]+cost[k][j])


                         cost[i][j]=cost[i][k]+cost[k][j];


          int station,money=oo;


          for (int i=0;i<N;i++)


          {


              int use=0;


              for (int j=0;j<K;j++)


                  if (!data[j].have_card)


                  {


                     use+=cost[data[j].start][i]*4;


                     if (cost[data[j].start][i]*4>data[j].money)


                     {


                        use=oo;


                        break;


                     }


                  }


                  else if (cost[data[j].start][i]==oo)


                  {


                       use=oo;


                       break;


                  }


              if (use<money)


              {


                 money=use;


                 station=i+1;


              }


          }


          if (money==oo) cout<<0<<endl;


          else cout<<station<<” “<<money<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


 

留下评论

电子邮件地址不会被公开。