求赞!
SPFA:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
queue<ll> q;
ll n,m,idx,dis[N],cnt[N],h[N],vtx[2*N],nxt[2*N],w[2*N];
bool vis[N];
void add(ll u,ll v,ll c) {
vtx[++idx]=v;
nxt[idx]=h[u];
h[u]=idx;
w[idx]=c;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(h,-1,sizeof(h));
cin>>n>>m;
for(ll i=1; i<=m; i++) {
ll x,y,z;
cin>>x>>y>>z;
add(x,y,z);
}
for(ll i=1; i<=n; i++) {
q.push(i);
vis[i]=1;
}
while(!q.empty()) {
ll u=q.front();
q.pop();
vis[u]=0;
for(ll i=h[u]; i!=-1; i=nxt[i]) {
ll v=vtx[i];
if(dis[v]>dis[u]+w[i]) {
dis[v]=dis[u]+w[i];
cnt[v]=cnt[u]+1;
if(cnt[v]>=n) {
cout<<"Yes";
return 0;
}
if(vis[v]==0) {
vis[v]=1;
q.push(v);
}
}
}
}
cout<<"No";
return 0;
}
BF
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2010,M=10010;
struct node {
ll u,v,c;
} e[M];
ll n,m,k,dis[N],lst[N];
bool flag;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(dis,0x3f,sizeof(dis));
cin>>n>>m;
for(ll i=1; i<=m; i++) {
ll x,y,z;
cin>>x>>y>>z;
e[i]= {x,y,z};
}
dis[1]=0;
for(ll i=1;i<=n;i++){
memcpy(lst,dis,sizeof(dis));
flag=false;
for(ll i=1; i<=m; i++) {
if (dis[e[i].v] >lst[e[i].u]+e[i].c){
dis[e[i].v]=lst[e[i].u]+e[i].c;
flag=true;
}
}
}
if(flag) cout<<"Yes";
else cout<<"No";
return 0;
}