POJ 3259: Wormholes

蟻本の問題番号と，問題名の対応が間違ってた．

概要

負閉路検知やるだけ．

const int INF = 100000000;
typedef int Weight;
struct Edge{
    int from, to;
    Weight weight;
    Edge(int f, int t, Weight w) : from(f), to(t), weight(w) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

bool findNegativeRoop(const Graph &g){
    int n = g.size();
    vector<Weight> dist(n, 0);
    for(int k = 0; k < n; ++k){
        for(int v = 0; v < n; ++v){
            EACH(i, g[v]){
                if(dist[i->to] > dist[i->from] + i->weight){
                    dist[i->to] = dist[i->from] + i->weight;
                    if(k == n-1) return true;
                }
            }
        }
    }
    return false;
}

int N, M, W;
int main(){
    int F;
    scanf("%d", &F);
    for(--F; F >= 0; --F){
        scanf("%d%d%d", &N,&M,&W);
        Graph g(N+1);
        for(int i = 0; i < M; ++i){
            int s, e, t;
            scanf("%d%d%d", &s, &e, &t);
            g[s].push_back(Edge(s, e, t));
            g[e].push_back(Edge(e, s, t));
        }
        for(int i = 0; i < W; ++i){
            int s, e, t;
            scanf("%d%d%d", &s, &e, &t);
            g[s].push_back(Edge(s, e, -t));
        }
        printf("%s\n", findNegativeRoop(g) ? "YES": "NO");
    }
    return 0;
}