求证:
a = b的情况下,只需要add(a, b, 0),而add(b, a, 0)是多余的。
PS:不加add(b, a, 0)的代码已AC,如下:\
// Problem: P1993 小 K 的农场
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1993
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Author: Leizijin
//
// Powered by CP Editor (https://cpeditor.org)
//
// 加边权的时候用一点小技巧就可以了
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<ll,ll>
#define il inline
#define fastio ios::sync_with_stdio(false), cin.tie(0)
const int N = 5e3+5;
const int inf = 0x3f;
int n,m;
vector<pii> G[N];
int dist[N], stp[N];
bool inq[N];
queue<int> Q;
bool SPFA(int s){
memset(stp, 0, sizeof(stp));
memset(dist, inf, sizeof(dist));
memset(inq, 0, sizeof(inq));
inq[s] = 1;
dist[s] = 0;
Q.push(s);
while(!Q.empty()){
int u = Q.front(); Q.pop();
inq[u] = 0;
if(stp[u] > n){
return false;
}
for(pii & ed : G[u]){
int v = ed.first, w = ed.second;
if(dist[u] + w < dist[v]){
dist[v] = dist[u] + w;
stp[v] = stp[u] + 1;
if(!inq[v]) inq[v] = 1, Q.push(v);
}
}
}
return true;
}
int main(){
fastio;
cin >> n >> m;
for(int i=1,opt,a,b,c; i<=m; i++){
cin >> opt;
if(opt == 1){
cin >> a >> b >> c; // a - b >= c(转换一下,b - a <= -c)
// G[a].pb({b, c});
G[a].pb({b, -c});
}
else if(opt == 2){
cin >> a >> b >> c;
G[b].pb({a, c}); // a - b <= c
}
else if(opt == 3){ // 这里不需要两头加?
cin >> a >> b;
G[b].pb({a, 0});
}
}
for(int i=1; i<=n; i++) G[0].pb({i, 0});
bool delta = SPFA(0);
if(delta){
printf("Yes\n");
}
else{
printf("No\n");
}
return 0;
}