SPFA求解
布局 Layout
https://ac.nowcoder.com/acm/problem/50390
#include <bits/stdc++.h> using namespace std; const int N=1005; const int M=10005+10005+1005; const int INF=0x3f3f3f3f; int n, m1, m2, E=0; int head[N], cnt[N], dist[N]; bool vis[N]; struct Edge{int v, w, ne;}e[M]; // 判环&求SSSP inline void add(int a, int b, int c){ e[E].v=b; e[E].w=c; e[E].ne=head[a]; head[a]=E++; } bool spfa(int k){ memset(cnt, 0x00, sizeof cnt); memset(vis, 0x00, sizeof vis); memset(dist, 0x3f, sizeof dist); queue<int> q; for(int i=1; i<=k; ++i){ q.push(i); vis[i]=true; dist[i]=0; } while(!q.empty()){ int node=q.front(); q.pop(); vis[node]=false; for(int i=head[node]; ~i; i=e[i].ne){ int v=e[i].v; if(dist[v]>dist[node]+e[i].w){ dist[v]=dist[node]+e[i].w; cnt[v]=cnt[node]+1; if(cnt[v]==n) return true; if(!vis[v]){ q.push(v); vis[v]=true; } } } } return false; } int main(){ memset(head, -1, sizeof head); cin>>n>>m1>>m2; int a, b, c; for(int i=0; i<m1; ++i){ cin>>a>>b>>c; if(a>b) swap(a, b); // 部分OJ未保证数据有序 add(a, b, c); } for(int i=0; i<m2; ++i){ cin>>a>>b>>c; if(a>b) swap(a, b); add(b, a, -c); } for(int i=1; i<n; ++i){ add(i+1, i, 0); } if(spfa(n)) {cout<<-1<<endl; return 0;} // 存在负环 else{ spfa(1); if(dist[n]==INF) {cout<<-2<<endl; return 0;} else cout<<dist[n]<<endl; } return 0; }