P1027 Car的旅行路线

admin

https://www.luogu.com.cn/problem/P1027

题目描述

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



图例（从上而下）

机场
高速铁路
飞机航线

注意：图中并没有标出所有的铁路与航线。

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

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

输入格式
第一行为一个正整数 n，表示有 n 组测试数据。

每组的第一行有 4 个正整数 s,t,A,B。

S表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B 的序号。

接下来有 S 行，其中第 i 行均有 7 个正整数xi1 ,yi1 ,xi2 ,yi2 ,xi3 ,yi3 ,Ti ，这当中的 (xi1,yi1)，(xi2,yi2)，(xi3,yi3)分别是第 i 个城市中任意 3 个机场的坐标，Ti为第 i 个城市高速铁路单位里程的价格。

输出格式
共有 n 行，每行 1 个数据对应测试数据。
保留一位小数。

输入输出样例
输入
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.5
说明/提示
【数据范围】
对于 100% 的数据，1≤n≤10，1≤S≤100，1≤A,B≤S

【题目来源】

NOIP 2001 提高组第四题


【思路】典型的D方法，难的不是D的模板，是建图，几乎所有的图论的题目难的都是建图，建好图之后将模板跑一下就得结果了。
【做法】我采用步步为营的做法，首先，先读入数据，求出第四个顶点，输出结果看看，保证求得正确；然后分两步生成邻接表，市内的出租车和城市间的飞机，要记得这是双向的，所以每次写入其实要正向反向各一次，然后打出来这个邻接表看看。最后当然就是Dijistra方法，直接上模板。

1. #include<iostream>
   
2. #include<iomanip>
   
3. #include<cmath>
   
4. using namespace std;
   
5. 
   
6. const int inf=2147483647;
   
7. const double eps=0.001;
   
8. const int mm=500*4*2;  //算500个点这样足够了
   
9. const int mn=500;
   
10. int n,s,t,A,B;
    
11. double xi1,xi2,xi3,xi4,yi1,yi2,yi3,yi4;
    
12. double T,w;
    
13. double cityx[mn],cityy[mn];//城市四个点
    
14. 
    
15. int nxt[mm],ev[mm],me;
    
16. double ew[mm];
    
17. int vist[mn],nbs[mn];
    
18. double dist[mn];
    
19. 
    
20. double sqr(double x){return x*x;}
    
21. double d(double x1,double y1,double x2,double y2)
    
22. {    return sqrt(sqr(x1-x2)+sqr(y1-y2));}
    
23. 
    
24. void calc4(double x1,double y1,double x2,double y2,double x3,double y3,double & x4,double & y4)
    
25. {
    
26.     double t12,t13,t23;
    
27.     t12=d(x1,y1,x2,y2);
    
28.     t13=d(x1,y1,x3,y3);
    
29.     t23=d(x3,y3,x2,y2);///注意判断的技巧，实数一般不直接比较相等
    
30.     if (abs(sqr(t12)+sqr(t13)-sqr(t23))<eps) x4=x2+x3-x1,y4=y2+y3-y1;
    
31.     else if (abs(sqr(t12)+sqr(t23)-sqr(t13))<eps) x4=x1+x3-x2,y4=y1+y3-y2;
    
32.     else if (abs(sqr(t13)+sqr(t23)-sqr(t12))<eps) x4=x1+x2-x3,y4=y1+y2-y3;
    
33. }
    
34. int getmin()
    
35. {
    
36.     int m,k,i;
    
37.     m=inf;
    
38.     k=0;  ///起点，无路可找的时候就返回0。此题全连通当然不会出现
    
39.     ///for (i=1;i<=n;i++)  cout<<dist[i]<<' '; cout<<endl;
    
40.     for (i=1; i<=4*s+1; i++)
    
41.         if (!vist[i]) if (dist[i]<m) {m=dist[i];k=i;}
    
42.     return k;
    
43. }
    
44. void dijkstra(int src,int dst)
    
45. {
    
46.     int i,j,u,v;
    
47.     for(i=1; i<=4*s+1; i++) { dist[i]=inf;vist[i]=0;};
    
48.     dist[src]=0;
    
49.     while(!vist[dst])
    
50.     {
    
51.         u=getmin();vist[u]=1;
    
52.         for(j=nbs[u]; j!=0; j=nxt[j])
    
53.         {
    
54.             v=ev[j];
    
55.             if(!vist[v]&&dist[u]+ew[j]<dist[v]) dist[v]=dist[u]+ew[j];
    
56.         }
    
57.     }
    
58. }
    
59. void checktable()///检查用
    
60. {
    
61.     for (int ii=0; ii<=4*s+1; ii++)
    
62.     {
    
63.         cout<<endl<<ii<<' '<<nbs[ii]<<' '<<endl;
    
64.         for(int jj=nbs[ii]; jj!=0; jj=nxt[jj])  cout<<setw(8)<<jj<<' ';
    
65.         cout<<endl;
    
66.         for(int jj=nbs[ii]; jj!=0; jj=nxt[jj])  cout<<setw(8)<<ev[jj]<<' ';
    
67.         cout<<endl;
    
68.         for(int jj=nbs[ii]; jj!=0; jj=nxt[jj])  cout<<setw(8)<<ew[jj]<<' ';
    
69.         cout<<endl;
    
70.     }
    
71. }
    
72. void init()///初始化
    
73. {
    
74.     int i;///好像其实某些也可以不用清零的
    
75.     for(i=0; i<=mm-1; i++)nxt[mm]=ev[mm]=ew[mm]=0;
    
76.     for(i=0; i<=mn-1; i++)nbs[mn]=0;
    
77.     me=0;
    
78. }
    
79. int main()
    
80. {
    
81.     cin>>n;while (n--) ///巧妙的少设一个变量
    
82.     {
    
83.         init(); ///清邻接表，最短路表等
    
84.         cin>>s>>t>>A>>B;
    
85.         for(int is=1; is<=s; is++) ///is表示第几个城市
    
86.         {
    
87.             cin>>xi1>>yi1>>xi2>>yi2>>xi3>>yi3>>T;
    
88.             ///求出第四个机场的位置
    
89.             calc4(xi1,yi1,xi2,yi2,xi3,yi3,xi4,yi4);
    
90.             ///保存市内交通到邻接表
    
91.             cityx[4*is-3]=xi1;
    
92.             cityx[4*is-2]=xi2;
    
93.             cityx[4*is-1]=xi3;
    
94.             cityx[4*is-0]=xi4;
    
95. 
    
96.             cityy[4*is-3]=yi1;
    
97.             cityy[4*is-2]=yi2;
    
98.             cityy[4*is-1]=yi3;
    
99.             cityy[4*is-0]=yi4;
    
100. 
     
101. 
     
102.             for (int ii=4*is-3; ii<=4*is-1; ii++)
     
103.                 for (int jj=ii+1; jj<=4*is; jj++)
     
104.                 {
     
105.                     w=T*d(cityx[ii],cityy[ii],cityx[jj],cityy[jj]);
     
106. 
     
107.                     nxt[++me]=nbs[ii];
     
108.                     nbs[ii]=me;
     
109.                     ev[me]=jj;
     
110.                     ew[me]=w;
     
111. 
     
112.                     nxt[++me]=nbs[jj];
     
113.                     nbs[jj]=me;
     
114.                     ev[me]=ii;
     
115.                     ew[me]=w;
     
116. 
     
117.                 }
     
118. 
     
119. 
     
120.             ///计算和前面的所有城市的机场交通并保存
     
121. 
     
122.             for (int ii=1; ii<=4*is-4; ii++)
     
123.                 for (int jj=4*is-3; jj<=4*is; jj++)
     
124. 
     
125.                 {
     
126.                     w=t*d(cityx[ii],cityy[ii],cityx[jj],cityy[jj]);
     
127.                     nxt[++me]=nbs[ii];
     
128.                     nbs[ii]=me;
     
129.                     ev[me]=jj;
     
130.                     ew[me]=w;
     
131. 
     
132.                     nxt[++me]=nbs[jj];
     
133.                     nbs[jj]=me;
     
134.                     ev[me]=ii;
     
135.                     ew[me]=w;
     
136.                 }
     
137. 
     
138. 
     
139. 
     
140.             ///加入起点和终点
     
141.             for (int jj=4*A-3; jj<=4*A; jj++)
     
142.             {
     
143.                 w=0;
     
144.                 nxt[++me]=nbs[0];
     
145.                 nbs[0]=me;
     
146.                 ev[me]=jj;
     
147.                 ew[me]=w;
     
148.             }
     
149. 
     
150.             for (int jj=4*B-3; jj<=4*B; jj++)
     
151.             {
     
152.                 w=0;
     
153.                 nxt[++me]=nbs[jj];
     
154.                 nbs[jj]=me;
     
155.                 ev[me]=4*s+1;
     
156.                 ew[me]=w;
     
157.             }
     
158. 
     
159.         }
     
160.         ///输出城市的四个点坐标 检查
     
161.         /*for (int ii=1; ii<=s; ii++)
     
162.         {
     
163.             cout<<endl<<ii<<endl;
     
164.             for (int jj=4*ii-3; jj<=4*ii; jj++)  cout<<cityx[jj]<<' '<<cityy[jj]<<endl;
     
165. 
     
166.         }
     
167. 
     
168.         ///输出邻接表 检查
     
169.         checktable();
     
170. 
     
171.         */
     
172.         dijkstra(0,4*s+1);
     
173.         cout<<fixed<<setprecision(1)<<dist[4*s+1];
     
174.     }
     
175.     return 0;
     
176. 
     
177. }
     
178. 
     

复制代码

admin

传上我2017年暑假在北大暑期学校现场做题的草稿，大家看看，做题之前先要怎么做。

admin

如前所说，这个题目算法并不难，但是那年在北大宿舍，很多同学一晚上都没有AC，于是第二天上午我亲自写了这个程序，大家仔细体会我是怎么做的：
1、事先有规划，（分析后选择算法，选好了中途基本就不要大改了，因为时间不够。具体需要哪几步解题，可能会有什么问题）
2、中间有检查，（第四个点的位置，邻接表等 这也是我经常强调的步步为营）
3、事后有反思。（如何优化，还可以这么样变简单，变难，还有什么其他的方法，比如此题可以SPFA）
这也是我们所有的OIer提高自己的科学的方法。