hnu 5校賽2008 problem題目大意

Problem

HOrienteering題目大意題目意思就是對于很多個計分點，要求一條從起點到終點的最短路徑，由于計分點小于等于

10個所以這個問題可以用狀態(tài)空間DP來解決。問題簡化為如何就各個節(jié)點可達(dá)路徑問題。如何構(gòu)造這個圖出來。由于題目的障礙物只是一個不自交的多邊形（而非凸多邊形），所以處理起來也不算麻煩。解題思路大致思路如下：將2個節(jié)點連線看線段是否穿過多邊形。穿過則不行。顯然如果只考慮計分點和起點終點的話這個圖是不對的。所以我們要將多邊形的節(jié)點一起考慮。這樣就可以得到一個包含了所有節(jié)點的圖了。對這個圖做一次

floyed就可以得到任意2點的最短距離。當(dāng)然我們只需要計分點和起點終點間的最短距離。算法線段與多邊形求交，判斷點和多邊形的位置關(guān)系 ---計算幾何部分

O（n3）floyed最短路--圖論部分O((n+m)3)狀態(tài)壓縮DP--動規(guī)部分O(2m

*m2)核心代碼：//連邊，將能夠直接到達(dá)的點連接起來。//本部分將能夠到達(dá)的點都連起來，構(gòu)圖。for(i=0;i<n;i++){for

(j=i+1;j<n;j++){flag=1;for

(k=m+2;flag

&&

k<n;k++){//當(dāng)前連線與多邊形障礙物相交if

(intersect(a[i],a[j],a[k],a[k+1])){flag=0;}}核心代碼：

for(k=m+2;flag

&&

k<n;k++)

{

//有多邊形的節(jié)點在線段上，排除特殊的相交情況

if

(k!=i

&&

k!=j

&&

online(a[i],a[j],a[k]))

{

flag=0;

}

}

if(flag)

{

//排除多邊形內(nèi)部連邊

}}mid.x=(a[i].x+a[j].x)/2;mid.y=(a[i].y+a[j].y)/2;if

(!(i>m+1

&&

j==i+1

||

i==m+2

&&

j==n-1)

&&

inside(mid))

flag=0;}if

(flag)

d[i][j]=d[j][i]=dist(a[i],a[j]);核心代碼：

//用floyed求對短路

for(k=0;k<n;k++)

{

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

if(i!=j

&&

d[i][j]

>

d[i][k]+d[k][j])

{

d[i][j] =

d[j][i]

=

d[i][k]+d[k][j];

}

}

}}核心代碼：狀態(tài)DP部分：for(i=0;i<1<<m;i++){for(j=0;j<m;j++){if(i

&

(1<<j)){for(k=0;k<m;k++){if(dp[(1<<k)|i][k]

>

dp[i][j]+d[j+2][k+2]){dp[(1<<k)|i][k]

=

dp[i][j]+d[j+2][k+2];}}}}}核心代碼：

double

ans

=

INF;for(i=0;i<m;i++){//printf("%.2lf

%.2lf\n",dp[1<<i][i],d[1][2+i]);if(ans

>

dp[(1<<m)-1][i]

+