c262 - 在巨人群中救回同伴是否搞錯了什麼
題目描述
題目描述了艾連需要穿越巨人群去拯救米卡莎。巨人群可以看作是一個圖，艾連從 1 號巨人出發，米卡莎在 n 號巨人處。每個巨人之間的移動都有一個危險值，艾連的能力值有限，如果艾連的能力值小於移動的危險值，則無法通過。題目要求判斷艾連是否能夠到達米卡莎處，如果能到達則輸出 "Save"，否則輸出 "GG"。
解題思路
這道題可以建模為一個帶權重的圖，其中每個巨人代表一個節點，巨人之間的移動危險值代表邊的權重。艾連的能力值 q 可以看作是允許的最大邊權。問題等價於判斷從節點 1 到節點 n 是否存在一條權重小於等於 q 的路徑。
可以使用 Floyd-Warshall 演算法來計算所有節點對之間的最小距離（危險值）。Floyd-Warshall 演算法可以有效地找到圖中任意兩點之間的最短路徑。在計算完所有節點對之間的最小距離後，檢查從節點 1 到節點 n 的距離是否小於等於 q。如果小於等於，則輸出 "Save"，否則輸出 "GG"。
程式碼中，a[i][j] 儲存了從巨人 i 到巨人 j 的危險值。如果沒有直接邊，則初始化為一個很大的值（2147483647）。然後，使用 Floyd-Warshall 演算法更新 a[i][j]，使其表示從巨人 i 到巨人 j 的最小危險值。
複雜度分析
- 時間複雜度: O(n^3)，其中 n 是巨人的數量。Floyd-Warshall 演算法的時間複雜度為 O(n^3)。
- 空間複雜度: O(n^2)，其中 n 是巨人的數量。需要一個 n x n 的矩陣來儲存圖的權重。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
#include <algorithm>
int a[501][501],n,m,q,x,y,v;
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
int main(){
while(n=read()){
m=read();
q=read();
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(i==j)
a[i][j]=0;
else
a[i][j]=2147483647;
while(m--){
x=read();
y=read();
v=read();
a[x][y]=v;
a[y][x]=v;
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
a[i][j]=std::min(a[i][j],std::max(a[i][k],a[k][j]));
if(a[1][n]<=q){
k=n+1;
i=n+1;
break;
}
}
if(a[1][n]>q){
putchar_unlocked('G');
putchar_unlocked('G');
putchar_unlocked('\n');
}
else{
putchar_unlocked('S');
putchar_unlocked('a');
putchar_unlocked('v');
putchar_unlocked('e');
putchar_unlocked('\n');
}
}
}