where
題意
雙向邊，及單向邊混合，問是否有環之路徑和為負。
思考
當一環之總和為負時，從該環之負值往隨便一方向走，沿途紀錄目前路徑值，而路徑值必定會是負的。
若以每個邊去檢查，那麼邊能不能是負的，或者說較小，那麼當檢查到 V 次的時候，就代表有一個負的環。
因為那個環是負的時候，它必定能夠一直更新，一直更小。
Code
#include <iostream>
#include <math.h>
#include <cstring>
using namespace std;
int T, N, M, W, X, dp[510];
//被坑點，edge[index][from, to, time]
int ed[6000][3];
void ini(void){
int i, j, k;
scanf("%d %d %d", &N, &M, &W);
memset(dp, 0, sizeof(dp));
X = (M<<1) + W;
i = 0;
//將雙向邊當作兩條單向邊
while(M--){
scanf("%d %d %d", ed[i], ed[i] + 1, ed[i] + 2);
i++;
ed[i][0] = ed[i - 1][1];
ed[i][1] = ed[i - 1][0];
ed[i][2] = ed[i - 1][2];
i++;
}
while(W--){
scanf("%d %d %d", ed[i], ed[i] + 1, ed[i] + 2);
//Wormholes 為負
ed[i][2] = 0 - ed[i][2];
i++;
}
}
void sol(void){
int i, j;
//最多跑 N 次去檢查
for(i = 0; i < N; i++){
//每個邊去做檢查是否能變小
for(j = 0; j < X; j++){
if(dp[ed[j][1]] > dp[ed[j][0]] + ed[j][2]){
dp[ed[j][1]] = dp[ed[j][0]] + ed[j][2];
//如果在第 N 次還能變小的話，代表有負環
if(i >= N - 1){
printf("YES\n");
return;
}
}
}
}
printf("NO\n");
return;
}
int main(void){
int i, j;
scanf("%d", &T);
while(T--){
ini();
sol();
}
}
被坑點
edge 陣列開不夠大 QAQ
忘記換算成單向應該是 (2M + W)