Car的旅行路線 [最短路]

2019-11-14 09:28:41

字體：大中小

供稿：網(wǎng)友

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

時(shí)間限制: 1 Sec 內(nèi)存限制: 128 MB

題目描述

又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每個城市都有四個飛機(jī)場，分別位于一個矩形的四個頂點(diǎn)上，同一個城市中兩個機(jī)場之間有一條筆直的高速鐵路，第i個城市中高速鐵路了的單位里程價(jià)格為Ti，任意兩個不同城市的機(jī)場之間均有航線，所有航線單位里程的價(jià)格均為t。

那么Car應(yīng)如何安排到城市B的路線才能盡可能的節(jié)省花費(fèi)呢?她發(fā)現(xiàn)這并不是一個簡單的問題，于是她來向你請教。

找出一條從城市A到B的旅游路線，出發(fā)和到達(dá)城市中的機(jī)場可以任意選取，要求總的花費(fèi)最少。

這里寫圖片描述

輸入

第一行有四個正整數(shù)s，t，A，B。

s表示城市的個數(shù)，t表示飛機(jī)單位里程的價(jià)格，A，B分別為城市A，B的序號，( 1 <= A，B <= s )。

接下來有S行，其中第I行均有7個正整數(shù)xi1，yi1，xi2，yi2，xi3，yi3，Ti，這當(dāng)中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分別是第i個城市中任意三個機(jī)場的坐標(biāo)，Ti為第i個城市高速鐵路單位里程的價(jià)格。

0 < S <= 100

輸出

輸出最小費(fèi)用(結(jié)果保留一位小數(shù))

樣例輸入

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

解題報(bào)告

太繁瑣了，沒什么好說的

#include<stdio.h>#include<queue>#include<cmath>#include<algorithm>#define MAX_N 102#define INF 0x3f3f3f3fusing 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);