在你要去的城市中,都有四个机场,且在一个平行四边形上,他们有地铁与相临的机场相连.城市间只有飞机可达.机票与地铁是按里程计算的,
机票是统一的,地铁由城市自定.由一个城市去另一个城市,
要找你在A城市到B城市的位置可以使花费最少;
#include<stdio.h>
#include<iostream.h>
#include<math.h>
#define max 20
#define INIT 1000;
/*
10
3
1 1 3 1 3 3 30
5 2 7 4 4 7 1
8 8 8 6 11 6 3
result
47.55
*/
//do the city
typedef class="tags" href="/tags/STRUCT.html" title=struct>struct
{
double x;
double y;
}point;
typedef class="tags" href="/tags/STRUCT.html" title=struct>struct
{
point pt[4];
int sttk;
}city;
//create the class="tags" href="/tags/GRAPH.html" title=graph>graph of city line
typedef class="tags" href="/tags/STRUCT.html" title=struct>struct en
{
int h;
double w;
en *next;
}enode;
typedef class="tags" href="/tags/STRUCT.html" title=struct>struct
{
en *next;
}vnode;
typedef class="tags" href="/tags/STRUCT.html" title=struct>struct
{
int pr;
double w;
}nb; //do the minline
class count
{
public:
int ctnum;
int flytk;
city ctbox[max];
vnode vbox[max];
nb nbox[max];
double que[max];
int m;
public:
count()
{
m=0;
cout<<"enter the fly ticket:";
cin>>flytk;
cout<<"enter the number of city:";
cin>>ctnum;
for(int i=0;i<ctnum;i++)
{
for(int j=0;j<3;j++)
{
cout<<"enter the point of city"<<i+1<<" of /npoint "<<j+1<<"(x,y):";
cin>>ctbox[i].pt[j].x>>ctbox[i].pt[j].y;
}
ctbox[i].pt[3]=getpt(ctbox[i].pt[0],ctbox[i].pt[1],ctbox[i].pt[2]);
cout<<"enter the city"<<i+1<<" stran ticket:";
cin>>ctbox[i].sttk;
}
//create the class="tags" href="/tags/GRAPH.html" title=graph>graph
for(i=0;i<ctnum*4;i++)
{
vbox[i].next=0;
}
for(i=0;i<ctnum;i++)
{
int n=i*4;
double l1,l2,l3,l4;
enode *p1=new enode;
enode *p2=new enode;
enode *p3=new enode;
enode *p4=new enode;
enode *p11=new enode;
enode *p22=new enode;
enode *p33=new enode;
enode *p44=new enode;
//the city self
l1=getlinelong(ctbox[i].pt[0],ctbox[i].pt[1])*ctbox[i].sttk;
l2=getlinelong(ctbox[i].pt[1],ctbox[i].pt[2])*ctbox[i].sttk;
l3=getlinelong(ctbox[i].pt[2],ctbox[i].pt[3])*ctbox[i].sttk;
l4=getlinelong(ctbox[i].pt[3],ctbox[i].pt[0])*ctbox[i].sttk;
p1->h=n+1;
p1->w=l1;
p1->next=vbox[n].next;
vbox[n].next=p1;
p11->h=n;
p11->w=l1;
p11->next=vbox[n+1].next;
vbox[n+1].next=p11;
p2->h=n+2;
p2->w=l2;
p2->next=vbox[n+1].next;
vbox[n+1].next=p2;
p22->h=n+1;
p22->w=l1;
p22->next=vbox[n+2].next;
vbox[n+2].next=p22;
p3->h=n+3;
p3->w=l3;
p3->next=vbox[n+2].next;
vbox[n+2].next=p3;
p33->h=n+2;
p33->w=l1;
p33->next=vbox[n+3].next;
vbox[n+3].next=p33;
p4->h=n;
p4->w=l4;
p4->next=vbox[n+3].next;
vbox[n+3].next=p4;
p44->h=n+3;
p44->w=l4;
p44->next=vbox[n].next;
vbox[n].next=p44;
//the city with city
for(int j=0;j<4;j++)
{
for(int k=0;k<i*4;k++)
{
enode *p=new enode;
enode *q=new enode;
p->h=n+j;
p->w=getlinelong(ctbox[k/4].pt[k%4],ctbox[i].pt[j])*flytk;
p->next=vbox[k].next;
vbox[k].next=p;
q->h=k;
q->w=p->w;
q->next=vbox[n+j].next;
vbox[n+j].next=q;
}
}
}
}
double getw(int i,int j)
{
enode *p=vbox[i].next;
while(p)
{
if(p->h==j)
return p->w;
p=p->next;
}
return INIT;
}
void road()
{
for(int i=0;i<4;i++)
for(int j=ctnum*4-1;j>ctnum*4-5;j--)
shortroad(i,j);
cout<<"/n/n";
double min=10000;
for(i=0;i<16;i++)
{
if(que[i]<min)
min=que[i];
}
cout<<"the mincount is:"<<min<<"/n/n"<<"the class="tags" href="/tags/PATH.html" title=path>path mincount"<<endl;
}
void shortroad( int v1,int v2)
{
int vs[max];
nb box[max];
for(int i=0;i<max;i++)
vs[i]=0;
vs[v1]=1;
for(i=0;i<ctnum*4;i++)
{
box[i].pr=v1;
box[i].w=getw(v1,i);
}
/* cout<<"/*8*88888888888888888888888/n/n";
for(i=0;i<ctnum*4;i++)
{
cout<<"the "<<i<<" :"<<box[i].pr <<" w:"<<box[i].w<<endl;
}
cout<<"/*8*88888888888888888888888/n/n";*/
for(i=1;i<ctnum*4;i++)
{
int n=getminline(vs);
vs[n]=1;
enode *p=vbox[n].next;
while(p)
{
int m=p->h;
if(vs[m]==0&&p->w+box[n].w<box[m].w)
{
box[m].w=p->w+box[n].w;
box[m].pr=n;
}
p=p->next;
}
}
que[m++]=box[v2].w;
cout<<"/n/n/n/n/n"<<"the :"<<box[v2].w<<" "<<que[m-1]<<endl;
printph(box,v2,v1);
}
int getminline(int *vs)
{
double min=INIT;
int n;
for(int i=0;i<ctnum*4;i++)
{
if(vs[i]==0)
{
if(nbox[i].w<min)
{
min=nbox[i].w;
n=i;
}
}
}
return n;
}
void printgh()
{
for(int i=0;i<ctnum*4;i++)
{
enode *p=vbox[i].next;
while(p)
{
cout<<i<<"----"<<p->w<<"-->"<<p->h<<endl;
p=p->next;
}
}
cout<<"/n/n"<<endl;
}
point getpt(point pt1,point pt2,point pt3) //the ring are pt1, pt2, pt3
{
double k1,k2;
point pt4;
if(pt1.x!=pt2.x&&pt2.x!=pt3.x)
{
k1=(pt1.y-pt2.y)/(pt1.x-pt2.x);
k2=(pt3.y-pt2.y)/(pt3.x-pt2.x);
pt4.x=(k2*pt1.x-k1*pt3.x+pt3.y-pt1.y)/(k2-k1);
pt4.y=k1*pt4.x-k1*pt3.x+pt3.y;
}
else
{
if(pt1.y==pt2.y)
{
pt4.x=pt1.x;
pt4.y=pt3.y;
}
else if(pt1.x==pt2.x)
{
pt4.x=pt3.x;
pt4.y=pt1.y;
}
}
return pt4;
}
double getlinelong(point pt1,point pt2)
{
double s,x,y;
x=(pt1.x-pt2.x)*(pt1.x-pt2.x);
y=(pt1.y-pt2.y)*(pt1.y-pt2.y);
s=sqrt(x+y);
return s;
}
void citypt()
{
for(int i=0;i<ctnum;i++)
{
cout<<"the city"<<i<<"th point/n";
for(int j=0;j<4;j++)
{
cout<<"the point "<<j<<":"<<"("<<ctbox[i].pt[j].x<<","<<ctbox[i].pt[j].y<<")/n";
}
cout<<"/n"<<endl;
}
}
void printph(nb *p,int i,int v)
{
cout<<i<<"<----";
int n=p[i].pr;;
while(n!=v)
{
printph(p,n,v);
return;
}
cout<<v<<"/n";
cout<<"the short class="tags" href="/tags/PATH.html" title=path>path!!/n";
}
};
void main()
{
count ct;
ct.citypt();
ct.printgh();
ct.road();
}
在vc6.0中通过,
注:在这中输入的三个城市的坐标是有序的.
