JZOJ_7.18C组第三题 最短路径

本文主要是介绍JZOJ_7.18C组第三题 最短路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

思路

动态规划。我们可以把去的路和来的路分开做，设$f[i][j]$表示第一个点走到$i$,第二个点(回去的那个点)走到$j$的最优值，可以得出动态转移方程:
$f[i][k]=min(f[i][k],f[i][j]+dis[j][k]$
$f[k][j]=min(f[k][j],f[i][j]+dis[i][k])$
至于特殊的两个点我们可以在枚举的时候进行特判。

代码

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int x[1001],y[1001],n,c1,c2;
double f[1001][1001],d[1001][1001];
int main()
{scanf("%d%d%d",&n,&c1,&c2);++c1;++c2;for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++)d[j][i]=d[i][j]=(double)sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));//两个点的直线距离 for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)f[i][j]=2147483647/3;f[1][1]=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){int k=max(i,j)+1;if(k==n+1)//特判n{if (i!=n) f[n][n]=min(f[n][n],f[i][j]+d[i][n]);if (j!=n) f[n][n]=min(f[n][n],f[i][j]+d[j][n]);continue;}if(k!=c1) f[i][k]=min(f[i][k],f[i][j]+d[j][k]);//特判特殊点if(k!=c2) f[k][j]=min(f[k][j],f[i][j]+d[i][k]);}printf("%.2lf",f[n][n]);
}

这篇关于JZOJ_7.18C组第三题 最短路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---