查看题目 Show Problem
题目:Car的旅行路线
问题编号:216 [提交该题] [讨论该问题] [有关讨论] [Who AC] [相关题解] [最优解]
My Flag:Unsubmited
题目类型
最短路
描述
又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。
图例
机场
高速铁路
飞机航线
注意：图中并没有
标出所有的铁路与航线。
那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。
任务
找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。
输出：到屏幕(输出最小费用，小数点后保留2位。)
输入格式
第一行为一个正整数n(0<=n<=10)，表示有n组测试数据。
每组的第一行有四个正整数s，t，A，B。
S(0<S<=100)表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，(1<=A，B<=S)。
接下来有S行，其中第I行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分别是第I个城市中任意三个机场的坐标，T I为第I个城市高速铁路单位里程的价格。
输出格式
共有n行，每行一个数据对应测试数据。(小数点保留2位)[RQ已经订正本题目]
样例输入
1
3 10 1 3
1 1 1 3 3 1 30
2 5 7 4 5 2 1
8 6 8 8 11 6 3
样例输出
47.55
*/
#include<iostream>
#include<cmath>
#include<climits>
using namespace std；
int n；
double t；
double x[401],y[401],ts[101]；
double dist[401][401]；
double dis[401][401]；
/*
struct link
{
int adjvex；
double len；
link *next；
}；
struct point
{
link *head；
} ps[401]；
*/
bool mark[401]；
int que[100001],front,rear；
void spfa(int q){
for (int j=1；j<=n*4；++j)
dis[q][j]=dist[q][j]；
memset(mark,false,sizeof(mark))；
front=rear=0；
que[rear++]=q；
mark[q]=true；
while (rear>front)
{
int i=que[front++]；
mark[i]=false；
front%=100001；
for (int j=1；j<=n*4；++j)
if (dis[q][j]>dis[q][i]+dis[i][j]){
dis[q][j]=dis[q][i]+dis[i][j]；
if (!mark[j])
{
mark[j]=true；
que[rear++]=j；
rear%=100001；
}
}
}
}
int main (void){
int w,a,b；
scanf ("%d",&w)；
for (int i=0；i<w；++i){
if (i!=0) printf("\n")；
int z；
scanf ("%d %d %d %d",&n,&z,&a,&b)；
t=(double)z；
// cout<<t<<endl；
for (int j=0；j<n；++j){
// ps[j+1].head=NULL；
int o[7]；
for (int k=0；k<7；k++)
scanf ("%d",&o[k])；
x[j*4+3]=(double)o[0]；
y[j*4+3]=(double)o[1]；
x[j*4+1]=(double)o[2]；
y[j*4+1]=(double)o[3]；
x[j*4+2]=(double)o[4]；
y[j*4+2]=(double)o[5]；
ts[j]=(double)o[6]；
for (int u=1；u<=3；++u)
for (int v=1；v<=3；++v)
if (u!=v&&((x[j*4+v]-x[j*4+u])*(x[j*4+6-u-v]-x[j*4+v])+(y[j*4+v]-y[j*4+u])*(y[j*4+6-u-v]-y[j*4+v]))==0){
x[j*4+4]=x[j*4+u]-x[j*4+v]+x[j*4+6-u-v]；
y[j*4+4]=y[j*4+u]-y[j*4+v]+y[j*4+6-u-v]；
break；
}
for (int u=j*4+1；u<=j*4+4；++u)
for (int v=j*4+1；v<=j*4+4；++v){
// cout<<x[u]<<’,’<<y[u]<<’ ’<<x[v]<<’,’<<y[v]<<’ ’<<endl；
dis[u][v]=ts[j]*sqrt(pow(x[u]-x[v],2)+pow(y[u]-y[v],2))；
// cout<<u<<’ ’<<v<<’ ’<<dis[u][v]<<endl；
// link *p1；
// p1=new link；
// p1->adjvex=v；
// p1->next=ps[u].head；
// p1->len=dis[u][v]；
// ps[u].head=p1；
}
}
for (int j=1；j<=n*4；++j)
for (int k=1；k<=n*4；++k)
if (!((j-k)>-4&&(j-k)<4)){
// cout<<x[j]<<’,’<<y[j]<<’ ’<<x[k]<<’,’<<y[k]<<’ ’<<endl；
dist[j][k]=pow(x[j]-x[k],2)+pow(y[j]-y[k],2)*t*t；
dist[j][k]=sqrt(dist[j][k])；
// cout<<j<<’ ’<<k<<’ ’<<dist[j][k]<<endl；
// link *p2；
// p2=new link；
// p2->adjvex=k；
// p2->next=ps[j].head；
// p2->len=dis[j][k]；
// ps[j].head=p2；
}
double min=(double)INT_MAX；
for (int j=(a-1)*4+1；j<=a*4；++j){
spfa(j)；
for (int k=(b-1)*4+1；k<=b*4；++k){
// printf ("%d ",dis[j][k])；
if (dis[j][k]<min) min=dis[j][k]；
}
// printf("\n")；
}
printf("%.2f",min)；
}
while (1)；
return 0；
}