Advertisement
Guest User

Untitled

a guest
Feb 27th, 2017
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.68 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef pair<int, int> ii;
  6. typedef vector<int> vi;
  7. typedef vector<ii> vii;
  8.  
  9.  
  10. #define INF 10000000
  11. int main()
  12. {
  13.     int V, E, s, u, v, w;
  14.  
  15.     //freopen("fucking.txt","wt",stdout);
  16.  
  17.  
  18.     int VE,dst;
  19.  
  20.     while(scanf("%d %d",&VE,&dst)==2)
  21.     {
  22.  
  23.         vector<vii> AdjList;
  24.         AdjList.assign(100000,vii());
  25.         vi cost;
  26.         for(int i=0; i<VE; i++)
  27.         {
  28.             int a;
  29.             scanf("%d",&a);
  30.             cost.push_back(a);
  31.  
  32.         }
  33.         map<int,int>mp;
  34.         vector<int>vt;
  35.  
  36.         getchar();
  37.  
  38.         int i,liftno;
  39.  
  40.         bool flag=false;
  41.  
  42.  
  43.  
  44.         for(i=0; i<VE; i++)
  45.         {
  46.             int inpt;
  47.  
  48.             stringstream ss;
  49.             ss.clear();
  50.             string s2;
  51.             getline(cin,s2);
  52.  
  53.  
  54.             ss<<s2;
  55.  
  56.             ss>>inpt;
  57.  
  58.             liftno = i*100;
  59.  
  60.             int j=1;
  61.  
  62.             while(j<=i)
  63.             {
  64.                 if(flag&&mp[liftno+inpt-j*100]>=1)
  65.                 {
  66.                     int k=liftno+inpt-j*100;
  67.  
  68.                     if(k==0)
  69.                     {
  70.                         AdjList[liftno+inpt-j*100].push_back(ii(liftno+inpt,0));
  71.                         AdjList[liftno+inpt].push_back(ii(liftno+inpt-j*100,0));
  72.                         //cout<<liftno+inpt-j*100<<' '<<liftno+inpt<<endl;
  73.  
  74.                     }else{
  75.                     AdjList[liftno+inpt-j*100].push_back(ii(liftno+inpt,60));
  76.                     AdjList[liftno+inpt].push_back(ii(liftno+inpt-j*100,60));
  77.                     }
  78.                     //cout<<liftno+inpt-j*100<<' '<<liftno+inpt<<endl;
  79.                 }
  80.                 j++;
  81.             }
  82.  
  83.  
  84.  
  85.  
  86.             vt.push_back(liftno+inpt);
  87.  
  88.             int u;
  89.             while(ss>>u)
  90.             {
  91.  
  92.                 vt.push_back(liftno+u);
  93.  
  94.                 j=1;
  95.  
  96.                 while(j<=i)
  97.                 {
  98.  
  99.                     if(flag&&mp[liftno+u-j*100]>=1)
  100.                     {
  101.                         int k=liftno+u-j*100;
  102.  
  103.                         if(k==0)
  104.                         {
  105.                             AdjList[liftno+u-j*100].push_back(ii(liftno+u,0));
  106.                             AdjList[liftno+u].push_back(ii(liftno+u-j*100,0));
  107.                             //cout<<liftno+u-j*100<<' '<<liftno+u<<endl;
  108.                         }
  109.                         else{
  110.                         AdjList[liftno+u-j*100].push_back(ii(liftno+u,60));
  111.                         AdjList[liftno+u].push_back(ii(liftno+u-j*100,60));
  112.                         //cout<<liftno+u-j*100<<' '<<liftno+u<<endl;
  113.                         }
  114.  
  115.  
  116.  
  117.  
  118.                     }
  119.                     j++;
  120.                 }
  121.  
  122.                 AdjList[liftno+inpt].push_back(ii(liftno+u,(u-inpt)*cost[i]));
  123.                 AdjList[liftno+u].push_back(ii(liftno+inpt,(u-inpt)*cost[i]));
  124.  
  125.                 //cout<<liftno+inpt<<' '<<liftno+u<<endl;
  126.  
  127.                 inpt = u;
  128.  
  129.             }
  130.             flag = true;
  131.             int sz = vt.size();
  132.  
  133.             for(int i=0; i<sz; i++)
  134.                 mp[vt[i]]++;
  135.             vt.clear();
  136.  
  137.         }
  138.  
  139.         /*cout<<AdjList[100].size()<<endl;
  140.         for(int i=0;i<AdjList[100].size();i++)
  141.         {
  142.             ii k = AdjList[100][i];
  143.             cout<<k.first<<' '<<k.second<<endl;
  144.         }*/
  145.  
  146.         vi dist(100000,INF);
  147.         dist[0] = 0;
  148.         dist[100]=0;
  149.         dist[200]=0;
  150.         dist[300]=0;
  151.         dist[400]=0;
  152.  
  153.         priority_queue< ii, vector<ii>, greater<ii> > pq;
  154.  
  155.         pq.push(ii(0, 0));
  156.         pq.push(ii(0, 100));
  157.         pq.push(ii(0, 200));
  158.         pq.push(ii(0, 300));
  159.         pq.push(ii(0, 400));
  160.  
  161.         while(!pq.empty())
  162.         {
  163.             bool flag = false;
  164.  
  165.             ii front = pq.top();
  166.             pq.pop();
  167.  
  168.             int d = front.first, u = front.second;
  169.  
  170.  
  171.             for (int j = 0; j < (int)AdjList[u].size(); j++)
  172.             {
  173.                 ii v = AdjList[u][j];
  174.                 //cout<<"--------"<<u<<' '<<v.first<<' '<<v.second<<endl;
  175.  
  176.  
  177.  
  178.                 if (dist[u] + v.second < dist[v.first])
  179.                 {
  180.  
  181.                     dist[v.first] = dist[u]+v.second;
  182.  
  183.                     pq.push(ii(dist[v.first], v.first));
  184.  
  185.  
  186.  
  187.                 }
  188.  
  189.  
  190.             }
  191.  
  192.         }
  193.  
  194.  
  195.  
  196.  
  197.         long long int rs = INF;
  198.  
  199.         //cout<<dist[103]<<endl;
  200.         //cout<<dist[3]<<endl;
  201.         //cout<<dist[203]<<endl;
  202.  
  203.  
  204.         for(int i=0; i<5; i++)
  205.             if(rs>dist[i*100+dst])
  206.                 rs = dist[i*100+dst];
  207.  
  208.         if(rs==INF)
  209.             printf("IMPOSSIBLE\n");
  210.         else
  211.             printf("%lld\n",rs);
  212.  
  213.     }
  214.  
  215.     return 0;
  216. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement