第一次做判环 然后RE了五次 死在了奇怪的点
memset(vis, 0, sizeof dis);
memset(dis, 0, sizeof vis);
什么鬼?? 什么鬼??
其实代码本身还是不难的 就是spfa另外开个数组记录入队次数
spfa不用写cmp真是太好了 operator什么的真的搞不清
#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; struct Node{ double c;//commission double r;//rate int point; int next; }node[1010]; int size, head[1010]; int n, m, s; double sq; void add(int from, int to, double rate, double commission) { node[size].r = rate; node[size].c = commission; node[size].point = to; node[size].next = head[from]; head[from] = size++; } bool spfa() { double dis[1010]; int count[1010]; bool vis[1010]; memset(count, 0, sizeof count); memset(dis, 0, sizeof dis); memset(vis, false, sizeof vis); queue<int> q; q.push(s); dis[s] = sq; vis[s] = true; while(!q.empty()){ int u = q.front(); q.pop(); vis[u] = false; for(int i = head[u]; ~i; i = node[i].next){ int j = node[i].point; if(dis[j] < (dis[u] - node[i].c) * node[i].r){ dis[j] = (dis[u] - node[i].c) * node[i].r; if(!vis[j]){ q.push(j); vis[j] = true; count[j]++; if(count[j] > n) return true; } } } } return false; } int main() { while(~scanf("%d%d%d%lf", &n, &m, &s, &sq)){ size = 0; memset(head, -1, sizeof head); while(m--){ int from, to; double r1, c1, r2, c2; scanf("%d%d%lf%lf%lf%lf", &from, &to, &r1, &c1, &r2, &c2); add(from, to, r1, c1); add(to, from, r2, c2); } if(spfa()) puts("YES"); else puts("NO"); } return 0; }