1.cpp

07年数学建模b题

//Cbus.h 
#include<fstream> 
#include<vector> 
using namespace std; 
extern int Station[3958]; 
struct Cost 
{ 
    int bus; 
    int station; 
    int cost; 
    int time; 
}; 
struct SmallCost 
{ 
    int cost; 
    int time; 
}; 
struct DotLine 
{ 
    int station; 
    vector<int>bus; 
}; 
extern vector<DotLine> Bus_train; 
ostream &operator<<(ostream &fcout,Cost &cost); 
class Bus 
{ 
public: 
    int m_num; 
    int m_cost; 
    int m_station[150]; 
    int m_flag; 
    Bus(); 
    int isexist(int p); 
    void rdouble(istream &fcin); 
    void rsingle(istream &fcin); 
    int getother(int p); 
    void Result(int p1,int p2,vector<Cost> &Rt,vector<Cost> &Rc,SmallCost &ti,SmallCost &co ); 
}; 
class Result 
{ 
public: 
    Bus m_bus[520]; 
    void subway(int p1,int p2,vector<Cost> &Rt,vector<Cost> &Rc, 
        SmallCost &ti,SmallCost &co); 
    int getmaxs(); 
    Result(); 
    void getResult(int p1,int p2,vector<Cost> &Rt,vector<Cost> &Rc, 
        SmallCost &ti,SmallCost &co); 
    void getResult1(int p1,int p2,vector<int> line1,vector<int> line2, 
                        vector<Cost> &Rt,vector<Cost> &Rc,SmallCost &ti,SmallCost &co); 
    void getResult2(int p1,int p2,vector<int> line1,vector<int> line2, 
                        vector<Cost> &Rt,vector<Cost> &Rc,SmallCost &ti,SmallCost &co); 
    vector<DotLine> getDotline(const Bus &b); 
}; 
vector<int> hash_cross(const Bus &b1,const Bus &b2); 
vector<int> hash_cross(const Bus &b); 

//bus.cpp 
#include<iostream> 
#include"Cbus.h" 
#include<math.h> 
using namespace std; 
extern vector<DotLine> Bus_train; 
Bus::Bus() 
{ 
    this->m_num=0; 
    this->m_cost=0; 
    this->m_flag=0; 
} 
void Bus::rdouble(istream &fcin) 
{ 
    int i=1; 
    while(fcin>>m_station[i]) 
    { 
        if(1==m_station[i]) 
            break; 
        m_station[i]=m_station[i]-10000; 
        i++; 
    } 
    m_station[0]=i-1; 
    i++; 
    while(fcin>>m_station[i]) 
    { 
        if(0==m_station[i]) 
            break; 
        m_station[i]=m_station[i]-10000; 
        i++; 
    } 
    m_station[m_station[0]+1]=i-m_station[0]-2; 
} 
void Bus::rsingle(istream &fcin) 
{ 
    int i=1;
if(m_flag!=2) 
    { 
        m_station[1]=m_flag-10000; 
        m_flag=1; 
        i++; 
    } 
    while(fcin>>m_station[i]) 
    { 
        if(0==m_station[i]) 
            break; 
        m_station[i]=m_station[i]-10000; 
        i++; 
    } 
    m_station[0]=i-1; 
} 

int Bus::isexist(int p) 
{ 
    int i=0; 
    if(0==this->m_flag) 
    { 
        for(i=1;i<=this->m_station[0];i++) 
        { 
            if(p==m_station[i]) 
                return i; 
        } 
        int temp=i+m_station[i]; 
        i++; 
        for(i;i<=temp;i++) 
        { 
            if(p==m_station[i]) 
                return i; 
        } 
    } 
    else 
    { 
        for(i=1;i<=this->m_station[0];i++) 
            if(p==m_station[i]) 
                return i; 
    } 
    return 0; 
} 
int Bus::getother(int p) 
{ 
    if(p>m_station[0]) 
        return 0; 
    for(int i=m_station[0]+1;i<m_station[0]+m_station[m_station[0]+1]+2;i++) 
        if(m_station[i]==m_station[p]) 
        { 
            return i; 
        } 
        return 0; 
} 
void Bus::Result(int p1,int p2,vector<Cost> &Rt,vector<Cost> &Rc,SmallCost &ti,SmallCost &co) 
{ 
     
    int q1,q2; 
    switch(m_flag) 
    { 
    case 0: 
        q1=getother(p1); 
        q2=getother(p2); 
        if(p1>p2&&p2>m_station[0]) 
            return; 
        if(p1>p2&&p1<m_station[0]&&q1==0&&q2==0) 
            return; 
        if( p1<p2 && ( p2<=m_station[0] || p1>=m_station[0] || (q1!=0&&q1<p2) )|| p1>p2&&q2>p1) 
        { 
            if(p1>p2) 
                p2=q2; 
            if(q1!=0&&q1<p2) 
                p1=q1; 
            Cost c; 
            c.bus=m_num; 
            c.station=m_station[p2]; 
            c.time=abs((p2-p1))*3; 
            if(m_cost) 
                c.cost=1; 
            else 
            { 
                c.cost=(abs(p2-p1)-1)/20+1; 
                c.cost=c.cost>3?3:c.cost; 
            } 
            if(c.cost<co.cost||(c.cost==co.cost && (Rc.size()>1 || c.time<co.time))) 
            { 
                Rc.clear(); 
                Rc.push_back(c); 
                co.cost=c.cost; 
                co.time=c.time; 
            } 
            if(c.time<ti.time||(c.time==ti.time && (Rt.size()>1 || c.cost<ti.cost))) 
            { 
                Rt.clear(); 
                Rt.push_back(c); 
                ti.time=c.time; 
                ti.cost=c.cost; 
                return; 
            } 
        } 
        else 
        { 
            if(p1>p2) 
            {     
                if(p1<m_station[0]) 
                    p1=q1; 
                Cost c; 
                Cost d; 
                c.bus=m_num; 
                c.station=m_station[1]; 
                c.time=(m_station[0]+m_station[m_station[0]+1]+1-p1)*3; 
                d.bus=m_num; 
                d.station=m_station[p2]; 
                d.time=abs(p2-1)*3; 
                if(m_cost) 
                { 
                    d.cost=1; 
                    c.cost=1; 
                } 
                else 
                { 
                    d.cost=(d.time/3-1)/20+1; 
                    c.cost=(c.time/3-1)/20+1; 
                    d.cost=d.cost>3?3:d.cost; 
                    c.cost=c.cost>3?3:d.cost; 
                } 
                if(c.time+d.time+5<ti.time||(c.time+d.time+5==ti.time&&c.cost+d.cost<ti.cost)) 
                { 
                    Rt.clear(); 
                    Rt.push_back(c); 
                    Rt.push_back(d); 
                    ti.time=c.time+d.time+5; 
                    ti.cost=c.cost+d.cost; 
                } 
                if(c.cost+d.cost<co.cost||(c.cost+d.cost==co.cost)&&c.time+d.time+5<co.time) 
                { 
                    Rc.clear(); 
                    Rc.push_back(c); 
                    Rc.push_back(d); 
                    co.cost=c.cost+d.cost; 
                    co.time=c.time+d.time+5; 
                } 
                return; 
            } 
            Cost c; 
            Cost d; 
            c.bus=m_num; 
            c.station=m_station[m_station[0]]; 
            c.time=abs(m_station[0]-p1)*3; 
            d.bus=m_num; 
            d.station=m_station[p2]; 
            d.time=abs(p2-m_station[0]-1)*3; 
            if(m_cost) 
            { 
                d.cost=1; 
                c.cost=1; 
            } 
            else 
            { 
                d.cost=(d.time/3-1)/20+1; 
                c.cost=(c.time/3-1)/20+1; 
                d.cost=d.cost>3?3:d.cost; 
                c.cost=c.cost>3?3:d.cost; 
            } 
            if(c.time+d.time+5<ti.time||(c.time+d.time+5==ti.time&&c.cost+d.cost<ti.cost)) 
            { 
                Rt.clear(); 
                Rt.push_back(c); 
                Rt.push_back(d); 
                ti.time=c.time+d.time+5; 
                ti.cost=c.cost+d.cost; 
            } 
            if(c.cost+d.cost<co.cost||(c.cost+d.cost==co.cost)&&c.time+d.time+5<co.time) 
            { 
                Rc.clear(); 
                Rc.push_back(c); 
                Rc.push_back(d); 
                co.cost=c.cost+d.cost; 
                co.time=c.time+d.time+5; 
            } 
            return;     
        } 
        break; 
    case 1: 
        Cost c; 
        c.bus=m_num; 
        c.station=m_station[p2]; 
        c.time=abs(p2-p1)*3; 
        if(m_cost) 
            c.cost=1; 
        else 
{ 
            c.cost=(abs(p2-p1)-1)/20+1; 
            c.cost=c.cost>3?3:c.cost; 
        } 
        if(c.cost<co.cost||(c.cost==co.cost && (Rc.size()>1 || c.time<co.time))) 
        { 
            Rc.clear(); 
            Rc.push_back(c); 
            co.cost=c.cost; 
            co.time=c.time; 
        } 
        if(c.time<ti.time||(c.time==ti.time && (Rt.size()>1 || c.cost<ti.cost))) 
        { 
            Rt.clear(); 
            Rt.push_back(c); 
            ti.time=c.time; 
            ti.cost=c.cost; 
            return; 
        }     
        break; 
    case 2: 
        int temp=abs(p1-p2); 
        c.bus=m_num; 
        c.station=m_station[p2]; 
        c.time=temp*3; 
        if(m_station[p1]==m_station[1]) 
        { 
            c.time=(p2-1<m_station[0]-p2?(p2-1)*3:abs(m_station[0]-p2)*3); 
        } 
        if(m_station[p2]==m_station[1]) 
        { 
            c.time=(p1-1<m_station[0]-p1?(p1-1)*3:abs(m_station[0]-p1)*3); 
        }     
        if(m_cost) 
            c.cost=1; 
        else 
        { 
            c.cost=(c.time/3-1)/20+1; 
            c.cost=c.cost>3?3:c.cost; 
        } 
        if(c.cost<co.cost||(c.cost==co.cost && (Rc.size()>1 || c.time<co.time))) 
        { 
            Rc.clear(); 
            Rc.push_back(c); 
            co.cost=c.cost; 
            co.time=c.time; 
        } 
        if(c.time<ti.time||(c.time==ti.time && (Rt.size()>1 || c.cost<ti.cost))) 
        { 
            Rt.clear(); 
            Rt.push_back(c); 
            ti.time=c.time; 
            ti.cost=c.cost; 
        } 
        if(p1==1||p2==1) 
            return; 
        int min=p2; 
        Cost d; 
        if(p1<p2) 
        { 
            p2=p1; 
            p1=min; 
            c.time=(p2-1)*3; 
            d.time=abs(m_station[0]-p1)*3; 
        } 
        else 
        { 
            c.time=abs(m_station[0]-p1)*3; 
            d.time=(p2-1)*3; 
        } 
        c.station=m_station[1]; 
        d.bus=c.bus; 
        d.station=m_station[min]; 
        if(m_cost) 
        { 
            c.cost=d.cost=1; 
        } 
        else 
        { 
            d.cost=(d.time/3-1)/20+1; 
            c.cost=(c.time/3-1)/20+1; 
            d.cost=d.cost>3?3:d.cost; 
            c.cost=c.cost>3?3:d.cost; 
        } 
        if(c.time+d.time+5<ti.time||(c.time+d.time+5==ti.time&&c.cost+d.cost<ti.cost)) 
        { 
            Rt.clear(); 
            Rt.push_back(c); 
            Rt.push_back(d); 
            ti.time=c.time+d.time+5; 
            ti.cost=c.cost+d.cost; 
        } 
        if(c.cost+d.cost<co.cost||(c.cost+d.cost==co.cost)&&c.time+d.time+5<co.time) 
        { 
            Rc.clear(); 
            Rc.push_back(c); 
            Rc.push_back(d); 
            co.cost=c.cost+d.cost; 
            co.time=c.time+d.time+5; 
        } 
        return; 
        break; 
    } 
} 
void Result::getResult(int p1,int p2,vector<Cost> &Rt,vector<Cost> &Rc, 
                       SmallCost &ti,SmallCost &co) 
{ 
    vector<int> line1,line2; 
    int flag=0,temp1=0,temp2=0; 
    ti.cost=ti.time=co.cost=co.time=999999999; 
    if(Station[p1]&&Station[p2]) 
        subway(p1,p2,Rt,Rc,ti,co); 
    for(int i=0;i<520;i++) 
    { 
        temp1=m_bus[i].isexist( p1 ); 
        if(temp1) 
        { 
            line1.push_back(i); 
            flag=1; 
        } 
        temp2=m_bus[i].isexist(p2); 
        if(temp2) 
        { 
            line2.push_back(i); 
            if(flag==1) 
                m_bus[i].Result(temp1,temp2,Rt,Rc,ti,co); 
        } 
        flag=0;     
    } 
    if(Station[p1]) 
        line1.push_back(1000); 
    if(Station[p2]) 
        line2.push_back(1000); 
   getResult1(p1,p2,line1,line2,Rt,Rc,ti,co); 
   getResult2(p1,p2,line1,line2,Rt,Rc,ti,co); 
} 

void Result::getResult1(int p1,int p2,vector<int> line1,vector<int> line2, 
                        vector<Cost> &Rt,vector<Cost> &Rc,SmallCost &ti,SmallCost &co) 
{ 
    int i=0,j=0; 
    for(i=0;i<line1.size();i++) 
        for(j=0;j<line2.size();j++) 
        ...{ 
            if(line1.at(i)==line2.at(j)) 
                continue; 
            vector<int> cross; 
            if(line1.at(i)<520&&line2.at(j)<520) 
               cross=hash_cross( m_bus[line1.at(i)], m_bus[line2.at(j)] ); 
            else 
            { 
                if(line1.at(i)>520) 
                    cross=hash_cross(m_bus[line2.at(j)]); 
                else 
                    cross=hash_cross(m_bus[line1.at(i)]); 
            } 
            if(cross.size()==0) 
                continue; 
            for(int k=0;k<cross.size();k++) 
            { 
                int cro=cross.at(k); 
                int change_cost; 
                change_cost=5; 
SmallCost t1={999999999,999999999}; 
                SmallCost t2,c1,c2; 
                t2=c1=c2=t1; 
                vector<Cost> Rc1,Rc2,Rt1,Rt2; 
                int num1=line1.at(i),num2=line2.at(j); 
                if(num1==num2||p2==cro||p1==cro) 
                    continue; 
                if(num1<520&&num2<520) 
                { 
                    m_bus[num1].Result(m_bus[num1].isexist(p1),m_bus[num1].isexist(cro), 
                        Rt1,Rc1,t1,c1); 
                    m_bus[num2].Result(m_bus[num2].isexist(cro),m_bus[num2].isexist(p2), 
                        Rt2,Rc2,t2,c2); 
                    change_cost=5; 
                } 
                if(num1==1000) 
                { 
                    change_cost=7; 
                    subway(p1,cro,Rt1,Rc1,t1,c1); 
                    m_bus[num2].Result(m_bus[num2].isexist(cro),m_bus[num2].isexist(p2), 
                        Rt2,Rc2,t2,c2); 
                    if(Rt1.at(0).bus<0) 
                        change_cost=3; 
                } 
                if(num2==1000) 
                {