夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

今日は宿題の日

といってもあんまりやらなかったので精進量が少ない言い訳にはならなかったり

3259

ワームホールって問題やっと見つけた^^
ただのベルマンフォードだったけど色々実装みすったりとかで大量WA・・・
蟻本の負の閉路判定って本当にあれで出来るんでしょうか???

#include <cstdio>
#include <cstring>
struct edge { int from, to, cost; };
const int INF=10000*2500+1;
int f, n, m, w;
int total;
int d[505];
edge es[5100];
bool solve() {
    for (int i=0; i<=n; i++) d[i]=INF;
    d[1]=0;
    for (int i=1; i<n; i++) {
        for (int j=0; j<total; j++) {
            edge e=es[j];
            if (d[e.to]>d[e.from]+e.cost) {
                d[e.to]=d[e.from]+e.cost;
            }
        }
    }
    for (int i=0; i<total; i++) {
        if (d[es[i].to]>d[es[i].from]+es[i].cost) return true;
    }
    return false;
}
int main() {
    scanf("%d",&f);
    for (int ix=0; ix<f; ix++) {
        scanf("%d%d%d",&n,&m,&w);
        total=0;
        for (int i=0; i<m; i++) {
            scanf("%d%d%d",&es[total].from,&es[total].to,&es[total].cost);
            es[total+1].to=es[total].from;
            es[total+1].from=es[total].to;
            es[total+1].cost=es[total].cost;
            total+=2;
        }
        for (int i=0; i<w; i++) {
            int s, e, t; scanf("%d%d%d",&s,&e,&t);
            es[total].from=s;
            es[total].to=e;
            es[total].cost=t*(-1);
            total++;
        }
        if (solve()) puts("YES");
        else puts("NO");
    }
}
広告を非表示にする