2013年7月21日 星期日

[UVA]186 - Trip Routing

#include<iostream>
#include <map>
#include<climits>
using namespace std;
class des{
    public:
        des(){
            value=INT_MAX;
            fromID=-1;
            fConnect=false;
            passbyID=-1;
        };
        int value;
        int fromID;
        int passbyID;
        bool fConnect;
        string route;

};
int to_int(char const *s)
{
     if ( s == NULL || s[0] == '\0' )
     {
       return 0;
     }
     bool negate = (s[0] == '-');
     if ( *s == '+' || *s == '-' )
          ++s;
     int result = 0;
     while(*s)
     {
          if ( *s >= '0' && *s <= '9' )
          {
              result = result * 10  - (*s - '0');
          }
          else
              return 0;
          ++s;
     }
     return negate ? result : -result;
}
void Floyd_Warshall(des arrDes[101][101],int nAirportNum){
    for(int k=1;k<=nAirportNum;k++){
        for(int i=1;i<=nAirportNum;i++){
            for(int j=1;j<=nAirportNum;j++){
                    if(arrDes[i][k].fConnect&&arrDes[k][j].fConnect){
                        int temp=arrDes[i][k].value + arrDes[k][j].value;
                        if(temp<arrDes[i][j].value){
                            arrDes[i][j].value=temp;
                            arrDes[i][j].passbyID=k;
                            arrDes[i][j].fConnect=true;

                        }
                    }
            }
        }
    }
}
void printPath(des arrDes[101][101],int fromID,int toID,map<int,string> airport){
    if(arrDes[fromID][toID].passbyID==fromID){
        cout.flags(ios::left);
        string from=airport.find(fromID)->second;
        string to=airport.find(toID)->second;
        cout.width(21);
        cout<<from;
        cout.width(21);
        cout<<to;
        cout.width(11);
        cout<<arrDes[fromID][toID].route;
        cout.width(5);
        cout.flags(ios::right);
        cout<<arrDes[fromID][toID].value<<endl;
    }
    else{
        int passbyID=arrDes[fromID][toID].passbyID;
        printPath(arrDes,fromID,passbyID,airport);
        if(arrDes[passbyID][toID].passbyID==passbyID){
            cout.flags(ios::left);
            string from=airport.find(passbyID)->second;
            string to=airport.find(toID)->second;
            cout.width(21);
            cout<<from;
            cout.width(21);
            cout<<to;
            cout.width(11);
            cout<<arrDes[passbyID][toID].route;
            cout.flags(ios::right);
            cout.width(5);
            cout<<arrDes[passbyID][toID].value<<endl;
        }
        else
            printPath(arrDes,passbyID,toID,airport);
    }
}
int main(){
    char bufc[256];
    map<string,int> airportNameToID;
    map<int,string> airportIDToName;
    int nAirportNum=0;
    des arrDes[101][101];
    while(cin.getline(bufc,256)){
        string bufs(bufc);
        if(bufs=="")break;
        std::size_t found=bufs.find(",",0);
        string from=bufs.substr(0,found);
        bufs=bufs.substr(found+1,bufs.length());
        found=bufs.find(",",0);
        string to=bufs.substr(0,found);
        bufs=bufs.substr(found+1,bufs.length());
        found=bufs.find(",",0);
        string route=bufs.substr(0,found);
        bufs=bufs.substr(found+1,bufs.length());
        found=bufs.find(",",0);
        string miles=bufs.substr(0,found);
        bufs=bufs.substr(found+1,bufs.length());
        int fromID,toID;
        if(airportNameToID.find(from)!=airportNameToID.end()){
            fromID=airportNameToID.find(from)->second;
        }
        else{
            nAirportNum++;
            fromID=nAirportNum;
            airportNameToID.insert(pair<string,int>(from,fromID));
            airportIDToName.insert(pair<int,string>(fromID,from));
        }
        if(airportNameToID.find(to)!=airportNameToID.end()){
            toID=airportNameToID.find(to)->second;
        }
        else{
            nAirportNum++;
            toID=nAirportNum;
            airportNameToID.insert(pair<string,int>(to,toID));
            airportIDToName.insert(pair<int,string>(toID,to));
        }
        int nValue=to_int(miles.c_str());
        if(arrDes[fromID][toID].value>nValue){
            arrDes[fromID][toID].value=nValue;
            arrDes[fromID][toID].route=route;
            arrDes[fromID][toID].fromID=fromID;
            arrDes[fromID][toID].passbyID=fromID;
            arrDes[fromID][toID].fConnect=true;

            arrDes[toID][fromID].value=nValue;
            arrDes[toID][fromID].route=route;
            arrDes[toID][fromID].fromID=toID;
            arrDes[toID][fromID].passbyID=toID;
            arrDes[toID][fromID].fConnect=true;
        }

    }
    Floyd_Warshall(arrDes,nAirportNum);
    while(cin.getline(bufc,255)){
        string bufs(bufc);
        cout<<endl<<endl;
        std::size_t found=bufs.find(",",0);
        string from=bufs.substr(0,found);
        string to=bufs.substr(found+1,bufs.length());
        int fromID=airportNameToID.find(from)->second;
        int toID=airportNameToID.find(to)->second;
        cout<<"From                 To                   Route      Miles"<<endl;
        cout<<"-------------------- -------------------- ---------- -----"<<endl;
        printPath(arrDes,fromID,toID,airportIDToName);
        cout<<"                                                     -----"<<endl;
        cout.flags(ios::left);
        cout.width(42);
        cout<<"";
        cout.width(11);
        cout<<"Total";
        cout.flags(ios::right);
        cout.width(5);
        cout<<arrDes[fromID][toID].value<<endl;
    }
    return 0;
}

2013年7月18日 星期四

[UVA] 122 - Trees on the level solution

#include<iostream>
#include <string>
#include <queue>
#define Notc "not complete"
using namespace std;

int to_int(char const *s)
{
     if ( s == NULL || s[0] == '\0' )
     {
       return 0;
     }
     bool negate = (s[0] == '-');
     if ( *s == '+' || *s == '-' )
          ++s;
     int result = 0;
     while(*s)
     {
          if ( *s >= '0' && *s <= '9' )
          {
              result = result * 10  - (*s - '0');
          }
          else
              return 0;
          ++s;
     }
     return negate ? result : -result;
}
class node{
public:
    node(){
        value=-1;
        bLeft=0;
        bRight=0;
    }
    bool bLeft,bRight;
    node *left,*right;
    int value;

};
int LevelOrderTraversal(node *root){
    queue<node*> myqueue;
    queue<int> qAnswer;
    myqueue.push(root);
    while(!myqueue.empty()){
        node *ptr=myqueue.front();
        myqueue.pop();
        if(ptr->value==-1){
            cout<<Notc<<endl;
            return 1;

        }
        else{
            qAnswer.push(ptr->value);
            if(ptr->bLeft)
                myqueue.push(ptr->left);
            if(ptr->bRight)
                myqueue.push(ptr->right);
        }


    }
    bool whiteSpace=false;
    while(!qAnswer.empty()){
        if(whiteSpace) cout<<" ";
        cout<<qAnswer.front();
        qAnswer.pop();
        whiteSpace=true;
    }
    cout<<endl;

}
int main(){
    string tempV,tempP,bufs;


    int count_notc=0;
    node *root=new node();
    bool bRepeate=false;
    while(cin>>bufs){
        std::size_t comma=bufs.find(",",0);
       if(bufs.length()==2){
            if(bRepeate) {
                cout<<Notc<<endl;
                root->bLeft=false;
                root->bRight=false;
                root->value=-1;
                bRepeate=false;
                continue;
            }
            else{
                LevelOrderTraversal(root);
                root->bLeft=false;
                root->bRight=false;
                root->value=-1;
                bRepeate=false;
                continue;
            }
       }
       tempV=bufs.substr(1,comma-1);
       tempP=bufs.substr(comma+1,bufs.find(")",0)-comma-1);
       int value=to_int(tempV.c_str());
       node *ptr;
       ptr=root;
       if(tempP!=""){
            for(int i=0;i<tempP.length();i++){
               if(tempP[i]=='L'){
                    if(!ptr->bLeft){
                        ptr->left=new node();
                        ptr->bLeft=true;
                    }
                    ptr=ptr->left;
               }
                else if(tempP[i]=='R'){
                    if(!ptr->bRight){
                        ptr->right=new node();
                        ptr->bRight=true;
                    }
                    ptr=ptr->right;
               }
            }
       }
        if(ptr->value!=-1){
            bRepeate=true;
            continue;
        }
        else
            ptr->value=value;
   }
    return 0;
}