P.S.o(︶︿︶)o 唉~虽然这题方程不难，但题目长，代码长，我花了超过3小时！(＞﹏＜)悲伤辣么大~~~ 谨此题解惠及众人，hh。

题意：给定长度为M的一串颜色序列，和平面上的N个颜色隧道。要求以颜色序列的顺序通过颜色隧道。（隧道可多次使用，可交叉，互不相同。）问从源点到汇点依次通过颜色的最小距离。

解法：f[i][j]表示通过颜色序列前 i 个颜色，这次的第 i 个颜色的隧道选 j 的最小距离。枚举第 i-1 个颜色选的隧道为 k ，则：f[i][j] = min( f[i][j] , f[i-1][k] + dis( a[k].xx , a[k].yy , a[j].x , a[j].y) + a[j].l );

我是规定每个隧道从(x,y)到(xx,yy)通过，所以读入时存2*N个隧道，(x,y)和(xx,yy)调换。这样就可以减去大部分人分f[i][j][0] 和 f[i][j][1]的多情况分析讨论，具体优越处见代码。

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<iostream>

 5 #include<algorithm>

 6 #include<cmath>

 7 using namespace std;

 8 #define M 35

 9 #define N 65

10 #define C 105

11 #define INF 2e9

12

13 int m,n;

14 double xs,ys,xt,yt;

15 int q[M];

16 struct node{double x,y,xx,yy,l;int c;};

17 node a[2*N];

18 double f[2][2*N];

19

20 void ins(int id,double x,double y,double xx,double yy,int c)

21 {

22     a[id].x=x,a[id].y=y,a[id].c=c;

23     a[id].xx=xx,a[id].yy=yy;

24     a[id].l=sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));

25 }

26 double mmin(double x,double y) {return x<y?x:y;}

27 double dis(double x,double y,double xx,double yy) {return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));}

28

29 int main()

30 {

31     int T,i,j,k;

32     scanf("%d",&T);

33     while (T--)

34     {

35       scanf("%lf%lf%lf%lf",&xs,&ys,&xt,&yt);

36       scanf("%d",&m);

37       for (i=1;i<=m;i++) scanf("%d",&q[i]);

38       scanf("%d",&n);

39       for (i=1;i<=n;i++)

40       {

41         double x,y,xx,yy;int c;

42         scanf("%lf%lf%lf%lf%d",&x,&y,&xx,&yy,&c);

43         ins(2*i-1,x,y,xx,yy,c),ins(2*i,xx,yy,x,y,c);

44       }

45       n*=2;

46

47       double ans=INF;

48       for (j=1;j<=n;j++)

49       {

50         if (a[j].c!=q[1]) continue;

51         f[1][j]=dis(xs,ys,a[j].x,a[j].y)+a[j].l;

52         if (m==1) ans=mmin(ans,f[1][j]+dis(a[j].xx,a[j].yy,xt,yt));//xx,yy

53       }

54       int u=1;

55       for (i=2;i<=m;i++)

56       {

57         u=1-u;

58         for (j=1;j<=n;j++)

59         {

60           f[u][j]=INF;

61           if (a[j].c!=q[i]) continue;

62           for (k=1;k<=n;k++)

63           {

64             if (a[k].c!=q[i-1]) continue;

65             f[u][j]=mmin(f[u][j],f[1-u][k]+dis(a[k].xx,a[k].yy,a[j].x,a[j].y)+a[j].l);

66           }

67           if (i==m) ans=mmin(ans,f[u][j]+dis(a[j].xx,a[j].yy,xt,yt));//xx,yy

68         }

69       }

70       printf("%.4lf\n",ans);

71     }

72     return 0;

73 }

我的方法+滚动数组

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<iostream>

 5 #include<cmath>

 6 using namespace std;

 7

 8 const int N=110,M=110;

 9 const double INF=(double)1e9;

10 int n,m;

11 int c[N];

12 double d[N][M][2];

13 struct node{double x,y;};

14 struct edge{node s,d;double len;int c;}a[N];

15 double minn(double x,double y){return x<y ? x:y;}

16 double dist(node t1,node t2){

17     return sqrt((t1.x-t2.x)*(t1.x-t2.x)+(t1.y-t2.y)*(t1.y-t2.y));

18 }

19

20 int main()

21 {

22     int T;

23     scanf("%d",&T);

24     while(T--)

25     {

26         node st,ed;

27         scanf("%lf%lf%lf%lf",&st.x,&st.y,&ed.x,&ed.y);

28         scanf("%d",&n);

29         for(int i=1;i<=n;i++)

30             scanf("%d",&c[i]);

31         scanf("%d",&m);

32         for(int i=1;i<=m;i++)

33         {

34             scanf("%lf%lf%lf%lf%d",&a[i].s.x,&a[i].s.y,&a[i].d.x,&a[i].d.y,&a[i].c);

35             a[i].len=dist(a[i].s,a[i].d);

36         }

37         double mn=INF;

38         for(int i=1;i<=m;i++)

39         {

40             if(a[i].c==c[1])

41             {

42                 d[1][i][0]=dist(st,a[i].s)+a[i].len;

43                 d[1][i][1]=dist(st,a[i].d)+a[i].len;

44                 if(n==1) mn=minn(mn,minn(d[1][i][0]+dist(a[i].d,ed),d[1][i][1]+dist(a[i].s,ed)));

45             }

46         }

47         for(int i=2;i<=n;i++)

48         {

49             for(int j=1;j<=m;j++)

50             {

51                 d[i][j][0]=d[i][j][1]=INF;

52                 if(a[j].c!=c[i]) continue;

53                 for(int k=1;k<=m;k++)

54                 {

55                     if(a[k].c!=c[i-1]) continue;

56                     d[i][j][0]=minn(d[i][j][0],a[j].len+minn(d[i-1][k][0]+dist(a[k].d,a[j].s),d[i-1][k][1]+dist(a[k].s,a[j].s)));

57                     d[i][j][1]=minn(d[i][j][1],a[j].len+minn(d[i-1][k][0]+dist(a[k].d,a[j].d),d[i-1][k][1]+dist(a[k].s,a[j].d)));

58                     // printf("%d  %d  d1 = %.3lf  d2 = %.3lf\n",i,j,d[i][j][0],d[i][j][1]);

59                 }

60                 if(i==n) mn=minn(mn,minn(d[i][j][0],d[i][j][1]));//dist(a[j].d,ed)dist(a[j].s,ed)

61             }

62         }

63         printf("%.4lf\n",mn);

64     }

65     return 0;

66 }

他人的方法(from gyw)

P.S.而且我他人的方法我选的还是很简短的代码，我看oj上大部分人都是2千多Byte的。这2个代码是1千5、6百多Byte。

而我还打了另外一个PG，将颜色隧道按颜色排序了，j和k的循环量比原来的2*N减少了，但是由于排序是O(n log n)，N的数据范围也只是几十，所以这个反而速度慢一点。另外。。这个程序只拿了5分，我不知道为何WA，求助啊！●o●

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<iostream>

 5 #include<algorithm>

 6 #include<cmath>

 7 using namespace std;

 8 #define M 35

 9 #define N 65

10 #define C 105

11 #define INF 2e9

12

13 int m,n;

14 double xs,ys,xt,yt;

15 int q[M],s[C];

16 struct node{double x,y,xx,yy,l;int c;};

17 node a[2*N];

18 double f[2][2*N];

19

20 void ins(int id,double x,double y,double xx,double yy,int c)

21 {

22     a[id].x=x,a[id].y=y,a[id].c=c;

23     a[id].xx=xx,a[id].yy=yy;

24     a[id].l=sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));

25 }

26 bool cmp(node x,node y) {return x.c<y.c;}

27 double mmin(double x,double y) {return x<y?x:y;}

28 double dis(double x,double y,double xx,double yy) {return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));}

29

30 int main()

31 {

32     int T,i,j,k;

33     scanf("%d",&T);

34     while (T--)

35     {

36       scanf("%lf%lf%lf%lf",&xs,&ys,&xt,&yt);

37       scanf("%d",&m);

38       for (i=1;i<=m;i++) scanf("%d",&q[i]);

39       scanf("%d",&n);

40       for (i=1;i<=n;i++)

41       {

42         double x,y,xx,yy;int c;

43         scanf("%lf%lf%lf%lf%d",&x,&y,&xx,&yy,&c);

44         ins(2*i-1,x,y,xx,yy,c),ins(2*i,xx,yy,x,y,c);

45       }

46       n*=2;

47       sort(a+1,a+1+n,cmp);

48

49       int c,cc;

50       c=s[0]=a[0].c=0;

51       for (i=1;i<=n;i++)

52        if (a[i].c!=a[i-1].c)

53        {

54          while (c<a[i].c) s[++c]=i-1;

55          s[a[i].c]=i;

56        }

57       s[a[n].c+1]=n+1;

58

59       double ans=INF;

60       q[0]=0,q[m+1]=a[n].c+1;

61       ins(0,xs,ys,xs,ys,0),ins(n+1,xt,yt,xt,yt,a[n].c+1);

62       s[a[n].c+2]=n+2;

63       f[0][0]=0.0;

64

65       int u=1;

66       for (i=1;i<=m+1;i++)

67       {

68         c=q[i],cc=q[i-1];

69         for (j=s[c];j<s[c+1];j++)

70         {

71          f[u][j]=INF;

72          for (k=s[cc];k<s[cc+1];k++)

73            f[u][j]=mmin(f[u][j],f[1-u][k]+dis(a[k].xx,a[k].yy,a[j].x,a[j].y)+a[j].l);

74          if (i==m+1) ans=mmin(ans,f[u][j]);

75         }

76         u=1-u;

77       }

78       printf("%.4lf\n",ans);

79     }

80     return 0;

81 }

排序+滚动数组（WA）

最新文章

  1. linux系统下修改文件夹目录权限
  2. AngularJS 表单
  3. QT 调试时出现 During startup program exited with code 0xc0000135 错误
  4. iOS 一个app跳转另一个app并实现通信（如A跳到B并打开B中指定页面）
  5. 《鸟哥的linux私房菜》 - linux命令温故而知新
  6. 通过ajax访问Tomcat服务器web service接口时出现No &#39;Access-Control-Allow-Origin&#39; header问题的解决办法
  7. PHP获取远程网站的服务器时间
  8. TCP三次握手和四次挥手过程及套接字在各个过程中的状态解析
  9. scp输入密码问题
  10. 虚拟机固定IP访问外网配置
  11. DOM的event对象的属性和方法
  12. Linux 单用户模式的使用
  13. Go语言及Web框架Beego环境
  14. C# 读取网页JSON数据
  15. [译]Ocelot - Caching
  16. stark组件开发之分页
  17. 商业化博客平台原型制作分享-TypePad
  18. Matlab中classperf对象各属性解释[原创]
  19. python的一些科学计算的包
  20. 在pom.xml中使用distributionManagement将项目打包上传到nexus私服

热门文章

  1. 【MyBatis】MyBatis 连接池和事务控制
  2. LeetCode682 棒球比赛
  3. docker 容器和镜像的常用命令
  4. 【Docker】在Linux系统中安装Docker虚拟机、启动停止重启查看Docker命令
  5. mysql 需要内核级线程的支持，而不只是用户级线程，这样才能够有效的使用多个cpu
  6. 【Oracle】10g查看trace生成文件位置及文件名称
  7. Redis 实战 —— 05. Redis 其他命令简介
  8. 2021年【线上】第一性原理vasp技术实战培训班
  9. 使用 .NETCore自带框架快速实现依赖注入
  10. 浅谈前端常用脚手架cli工具及案例