正題

---

大意

有n個點，開始只能從前面的點走到后面的點，到達(dá)點n后返回，之后就只能從后面的點走到前面的點，從點1出發(fā)，要求每個點（除了點1）都必須且只能經(jīng)過一遍，并回到點1的最短路徑。給出每個點的坐標(biāo)。
有兩個點，一個必須在點n之前到達(dá)，一個必須在點n之后到達(dá)。

---

解題思路

因為這個可以看成一個無向圖，所有我們可以將路徑分為去和回兩條，然后把回去的路徑反過來，這就變成了求兩條路徑覆蓋所有點并且不重復(fù)還有兩個特殊點。
我們考慮dp，由于數(shù)據(jù)范圍可以n2n2，我們可以用f[i][j]f[i][j]表示第一條路徑到達(dá)第i個點，第二條路徑到達(dá)第j個點時的最短路。然后我們每次讓i和j交替向前，用一個k表示第i和第j個點先前走的最近距離。
然后動態(tài)轉(zhuǎn)移：

f[i][k]=min{f[i][j]+dis[j][k]}f[i][k]=min{f[i][j]+dis[j][k]}
f[k][j]=min{f[i][j]+dis[i][k]}f[k][j]=min{f[i][j]+dis[i][k]}
兩個特殊點就保證一個在第一維中沒有值一個保證在第二維中沒有值就好了。

---

代碼

#include<cstdio> #include<cmath> #include<algorithm> #define N 1010 #define inf 2147483647/3 using namespace std; double x[N],y[N],dis[N][N],f[N][N]; int n,b1,b2; double Dis(double x1,double y1,double x2,double y2) {return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));} int main() {scanf("%d%d%d",&n,&b1,&b2);b1++;b2++;for (int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);for (int i=1;i<n;i++) for (int j=i+1;j<=n;j++)dis[i][j]=dis[j][i]=Dis(x[i],y[i],x[j],y[j]);//計算距離for (int i=1;i<=n;i++)for (int j=1;j<=n;j++) f[i][j]=inf;//初始化f[1][1]=0;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){if (i==j&&i!=1)continue;int k=max(i,j)+1;if (k==n+1)//特判{if (i!=n) f[n][n]=min(f[n][n],f[i][j]+dis[i][n]);if (j!=n) f[n][n]=min(f[n][n],f[i][j]+dis[j][n]);continue;}if (k!=b1) f[i][k]=min(f[i][k],f[i][j]+dis[j][k]);if (k!=b2) f[k][j]=min(f[k][j],f[i][j]+dis[i][k]);//動態(tài)轉(zhuǎn)移}printf("%0.2lf",f[n][n]); }

總結(jié)

以上是生活随笔為你收集整理的jzoj3510-最短路径【dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。