判环模板题 有了上一题的经验过得很轻松
除了因为spfa还不是很熟打错了两个字母 然后debug了一小会
#include <iostream> #include <string> #include <cstdio> #include <cmath> #include <cstring> #include <queue> #include <map> #include <vector> #include <set> #include <algorithm> #define INF 0x3F3F3F3F using namespace std; int size, head[1010], next[6010], point[6010], val[6010]; void init() { size = 0; memset(head, -1, sizeof head); } void add(int from, int to, int value) { point[size] = to; val[size] = value; next[size] = head[from]; head[from] = size++; } bool spfa(int s, int n) { int dis[1010], time[1010]; bool vis[1010]; memset(dis, 0x3f, sizeof dis); memset(time, 0, sizeof time); memset(vis, false, sizeof vis); queue<int> q; q.push(s); dis[s] = 0; vis[s] = true; while(!q.empty()){ int u = q.front(); q.pop(); vis[u] = false; for(int i = head[u]; ~i; i = next[i]){ int j = point[i]; if(dis[j] > dis[u] + val[i]){ dis[j] = dis[u] + val[i]; if(!vis[j]){ //printf("dis[%d] = %d ", j, dis[j]); q.push(j); vis[j] = true; if(++time[j] > n) return true; } } } } return false; } int main() { int f, n, m, w; scanf("%d", &f); while(f--){ init(); scanf("%d%d%d", &n, &m, &w); while(m--){ int a, b, value; scanf("%d%d%d", &a, &b, &value); add(a, b, value); add(b, a, value); } while(w--){ int from, to, value; scanf("%d%d%d", &from, &to, &value); add(from, to , 0 - value); } if(spfa(1, n)) puts("YES"); else puts("NO"); } return 0; }