11492 - Babel

All about problems in Volume CXIV. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

11492 - Babel

Postby hotovaga » Mon Feb 21, 2011 7:59 am

This is my approach, I can't understand why I am getting WA.

Code: Select all
#include<iostream>
#include<utility>
#include<cstdio>
#include<vector>
#include<string>
#include<map>
#include<queue>

#define MAX_INT 1077952576

using namespace std;

int E,len;

int cost[2*2000+10],res;
bool visited[2*2000+10];

map<string,int>v;
vector< vector< pair< int,pair<int,char> > > > adjList(2000*2+10);
priority_queue<pair< int,pair<int,char> > > pq;

void initialize()
{
   
   int i,j;
   
    for(i = 0; i<=E*2; i++)
      cost[i] = MAX_INT;
   
         
   for(i =0; i<=E*2; i++)
      visited[i] = false;
      
   v.clear();
   
   adjList.clear();
   
   for(i=0;i<2*E;i++)
   adjList[i].clear();
   
   pq = priority_queue<pair< int,pair<int,char> > > ();
   res = MAX_INT;
}



int main()
{
   
   int i,j,k,u,d,cnt;
   
   

   while(scanf("%d",&E)==1){
      if(E==0)
      break;
   
        initialize();
      
       string s1,s2,s3;
      
        cin>>s1>>s2;
      
      cnt = 2;
       
       
      
      v[s1] = 0;  //source vertex indexed to 0
      if(v.find(s1) == v.find(s2)){
                      res  = 0;
                   
    }
      
      v[s2] = 1; //destination vertex indexed to 1
       
      for(i=0; i<E; i++){
         s1.clear();
         s2.clear();
         s3.clear();

         
         cin>>s1>>s2>>s3;

         if(v.find(s1) == v.end()){
            v[s1] = cnt;
            u = cnt++;
         }

         else
             u = v.find(s1)->second;

         if(v.find(s2) == v.end()){
            v[s2] = cnt;
            d = cnt++;
         }
         else
            d = v.find(s2)->second;

         len = s3.size();
      
         char ch = s3[0];

           
         adjList[u].push_back(make_pair(len,(make_pair(d,ch))));
         adjList[d].push_back(make_pair(len,(make_pair(u,ch))));
      }

      //end of taking input
//Dijkstra Begins
      cost[0] = 0;
   

   
      
      pair<int,pair<int,char> > cur, next;

      pq.push(make_pair(0,make_pair(0,'1')));
      
      

      while(!pq.empty()){
         cur = pq.top();
         pq.pop();

         cur.first = -cur.first;

         if(visited[cur.second.first])
            continue;
         visited[cur.second.first] = true;
      
         
         
         for(i = 0; i<adjList[cur.second.first].size(); i++){
                 
            next = adjList[cur.second.first][i];
            if(next.second.second == cur.second.second)
               continue;
            if(visited[next.second.first])
                    continue;

            int curcost = cost[cur.second.first] + next.first;
            
            
            if(curcost < cost[next.second.first]){
               cost[next.second.first] = curcost;
               }
            pq.push(make_pair(-curcost,make_pair(next.second.first,next.second.second)));
         }
      }

       if( res ==0 )
           printf("0\n");
      else if(cost[1]== MAX_INT)
         printf("impossivel\n");
      else
         printf("%d\n",cost[1]);
   }


   return 0;
}


Thanks in advance.
hotovaga
New poster
 
Posts: 4
Joined: Mon Nov 29, 2010 9:35 pm

Return to Volume CXIV

Who is online

Users browsing this forum: No registered users and 1 guest