d792 - 11463 - Commandos
題目描述
題目描述了一個圖論問題，其中 N 個建築物由 R 條道路連接。突擊隊需要從起始建築物 s 出發，訪問所有建築物，最後回到集合地點 d。目標是找到完成任務所需的最短時間，假設在每個建築物設置炸彈的時間可以忽略不計。
解題思路
這題可以建模為一個圖論問題。首先，使用給定的邊建立一個鄰接矩陣，表示建築物之間的距離。如果兩個建築物之間沒有直接連接，則距離設為一個很大的值（例如 10000000）。然後，使用 Floyd-Warshall 演算法計算所有建築物對之間的最短路徑。最後，對於每個中間建築物 i，計算從起始建築物 s 到 i 的最短路徑加上從 i 到集合地點 d 的最短路徑，並取最大值，即為完成任務所需的最短時間。
複雜度分析
- 時間複雜度: O(N^3)，其中 N 是建築物的數量。這是因為 Floyd-Warshall 演算法的時間複雜度為 O(N^3)。
- 空間複雜度: O(N^2)，其中 N 是建築物的數量。這是因為需要一個 N x N 的鄰接矩陣來存儲圖。
程式碼
#include <iostream>
using namespace std;
int a[105][105],n,t,r,s,d,g[105],ans;
/*void dfs(int time,int it,int total){
if(time>=ans)return;
else if(total==n){
ans=min(ans,time+a[it][d]);
return;
}
g[it]=1;
for(int i=0;i<n;++i){
if(g[i]==0){
dfs(time+a[it][i],i,total+1);
}
}
g[it]=0;
}*/
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
for(int ca=1;ca<=t;++ca){
ans=0;
cin >> n >> r;
for(int i=0;i<n;++i){
g[i]=0;
for(int j=0;j<n;++j){
a[i][j]=10000000;
if(i==j)a[i][j]=0;
}
}
for(int i=0;i<r;++i){
cin >> s >> d;
a[s][d]=a[d][s]=1;
}
for(int k=0;k<n;++k){
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
a[j][i]=a[i][j]=min(a[i][k]+a[k][j],a[i][j]);
}
}
}
cin >> s >> d;
for(int i=0;i<n;++i){
ans=max(a[s][i]+a[i][d],ans);
}
cout << "Case " << ca << ": " << ans << '\n';
}
}