HPUOJ 1219: Car的旅行路线 [最短路]

时间限制: 1 Sec 内存限制: 128 MB

题目描述

又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第i个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。

那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。

找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。

输入

第一行有四个正整数s，t，A，B。

s表示城市的个数，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个城市中任意三个机场的坐标，Ti为第i个城市高速铁路单位里程的价格。

0 < S <= 100

输出

输出最小费用(结果保留一位小数)

样例输入

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.5

解题报告

太繁琐了，没什么好说的

#include<stdio.h> #include<queue> #include<cmath> #include<algorithm> #define MAX_N 102 #define INF 0x3f3f3f3f using namespace std; struct city{int x[4],y[4],v;double val[4];}; city cs[MAX_N]; double d[MAX_N]; int E,V,T,A,B; double cost(int a,int b){ double min=1e9; for(int j=0;j<4;j++) for(int k=0;k<4;k++){ double dis=(cs[a].x[j]-cs[b].x[k])*(cs[a].x[j]-cs[b].x[k])+(cs[a].y[j]-cs[b].y[k])*(cs[a].y[j]-cs[b].y[k]); dis=sqrt(dis); double tmp=cs[a].val[j]+dis*T; if(tmp<cs[b].val[k]) cs[b].val[k]=tmp; if(cs[b].val[k]<min) min=cs[b].val[k]; } //update for(int j=0;j<4;j++) for(int k=j+1;k<4;k++){ double dis=(cs[b].x[j]-cs[b].x[k])*(cs[b].x[j]-cs[b].x[k])+(cs[b].y[j]-cs[b].y[k])*(cs[b].y[j]-cs[b].y[k]); dis=sqrt(dis); double tmp1=cs[b].val[j]+dis*cs[b].v; double tmp2=cs[b].val[k]+dis*cs[b].v; if(tmp1<cs[b].val[k]) cs[b].val[k]=tmp1; if(tmp2<cs[b].val[j]) cs[b].val[j]=tmp2; } return min; } void sfpa(int s){ //init fill(d,d+V+1,1e9); for(int i=1;i<=V;i++) for(int j=0;j<4;j++) cs[i].val[j]=1e9; d[s]=0.0; for(int i=0;i<4;i++) cs[s].val[i]=0.0; queue<int> que; que.push(s); while(!que.empty()){ int t=que.front();que.pop(); for(int i=1;i<=V;i++){ if(t==i) continue; double tmp=cost(t,i); if(tmp<d[i]){ d[i]=tmp; que.push(i); } } } } int main() { scanf("%d%d%d%d",&V,&T,&A,&B); for(int i=1;i<=V;i++){ scanf("%d%d%d%d%d%d%d",&cs[i].x[0],&cs[i].y[0],&cs[i].x[1],&cs[i].y[1],&cs[i].x[2],&cs[i].y[2],&cs[i].v); int d12=(cs[i].x[2]-cs[i].x[1])*(cs[i].x[2]-cs[i].x[1])+(cs[i].y[2]-cs[i].y[1])*(cs[i].y[2]-cs[i].y[1]); int d02=(cs[i].x[2]-cs[i].x[0])*(cs[i].x[2]-cs[i].x[0])+(cs[i].y[2]-cs[i].y[0])*(cs[i].y[2]-cs[i].y[0]); int d01=(cs[i].x[1]-cs[i].x[0])*(cs[i].x[1]-cs[i].x[0])+(cs[i].y[1]-cs[i].y[0])*(cs[i].y[1]-cs[i].y[0]); if(d12+d01==d02){ cs[i].x[3]=cs[i].x[0]+cs[i].x[2]-cs[i].x[1]; cs[i].y[3]=cs[i].y[0]+cs[i].y[2]-cs[i].y[1]; }else if(d12+d02==d01){ cs[i].x[3]=cs[i].x[0]+cs[i].x[1]-cs[i].x[2]; cs[i].y[3]=cs[i].y[0]+cs[i].y[1]-cs[i].y[2]; }else{ cs[i].x[3]=cs[i].x[2]+cs[i].x[1]-cs[i].x[0]; cs[i].y[3]=cs[i].y[2]+cs[i].y[1]-cs[i].y[0]; } } sfpa(A); printf("%0.1f\n",d[B]); return 0; }