SSLOJ 最短路

2022-09-23 02:02:02 字數 984 閱讀 5817

容易發現從 \(i\) 到 \(j\) 的最優路徑一定是先往右再往左。因為如果某一時刻往左走後再往右走,那麼還不如在往左走的時刻直接往右走。

所以考慮如何求出 \(dis[i][j]\) 表示只往右走,\(i\) 到 \(j\) 的最短路。

那麼可以考慮列舉 \(j\),然後從 \(j-1\) 到 1 列舉 \(i\),容易發現走相同步數,走的越右顯然更優,所以可以利用單調性求出 \(dis[i][j]\)。

然後用類似 spfa 的想法,列舉 \(i\),將 \(dis[i][j]\) 從小到大排序,向前染色。每個點最多被染色一次。

時間複雜度 \(o(n^2)\)。

#include using namespace std;

const int n=6010;

int n,ans,a[n],b[n],dis[n][n],father[n];

bool used[n];

vectorpos[n];

int find(int x)

int main()

} b[1]=1;

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

for (int j=i;j<=n;j++)

pos[dis[i][j]].push_back(j);

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

for (register int k=0;k=b[p];q=find(q))

}} for (register int i=1;i<=n;i++)

for (register int j=1;j<=n;j++)

ans^=(i+j)*dis[i][j];

printf("%d",ans);

return 0;

}

hdu 2544 最短路(最短路)

time limit1000 ms memory limit32768 kb 在每年的校賽裡,所有進入決賽的同學都會獲得一件很漂亮的t shirt。但是每當我們的工作人員把上百件的衣服從商店運回到賽場的時候,卻是非常累的!所以現在他們想要尋找最短的從商店到賽場的路線,你可以幫助他們嗎? input輸...

HDU 2544 最短路 (最短路,spfa)

題意 中文題目 思路 spfa slf優化。關於spfa的詳情請戳我 1 include 2 using namespace std 3const int n 105 inf 0x7f7f7f7f 4 intn m 5bool vis n 標記是否在佇列中 6int dest n 路徑長度 7int...

模板 最短路

堆優化,用距離最小的點更新其他節點。 void dijkstra int s bellman ford 的佇列優化。 每次把能更新且不在佇列...