[TIOJ] 1034. 搶救雷恩大兵 (Saving Ryan)
題目連結: http://tioj.infor.org/problems/1034 本題N超小的，估了一下到$O(N^6)$甚至$O(N^7)$可能都會過，不過該怎麼做這題呢XD 仔細想想我們如果可以快速得到任意兩點的最短距離的話，那就直接枚舉炸掉所有位置，看看哪樣比較短，也就是說答案就是$\min\limits_{\forall k \in V} dis[a][k]+dis[k][b]-2 \times val[k]$(其中v是所有點的集合)(這是先把二維圖轉一維後的寫法)，而任兩點最短路徑的話就直接寫個floyd-warshall就好了XD 不過說直接floyd-warshall很容易，但本題給的是點權，可能沒辦法好好做，所以我直接用了一個小技巧(或許可以不用用拉XD):把a到b的距離設成$2 \times val[b]-val[a]$，最後算a到b時再加回$2 \times val[a]-val[b]$他的值就會是好的了 #include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define N 20
#define INF 100000
int g[N+5][N+5];
lld sg[3000][3000];
int n;
inline int Hash(int,int);
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&g[i][j]);
for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int p=0;p<n;p++)for(int q=0;q<n;q++)sg[Hash(i,j)][Hash(p,q)]=INF;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
...