時間限制: 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 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);新聞熱點
疑難解答
