poj3259

传送门

第一种方法：Bellman-Ford

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m, w;
#define MAX 10005
struct node{
    int u, v, t;
}p[5210];

void Bellman_Ford(){
    int dis[505];
    memset(dis, MAX, sizeof(dis));
    dis[1] = 0;
    for(int i = 1; i < n; i++)
        for(int j = 1; j <= 2 * m + w; j++)
            dis[p[j].v] = min(dis[p[j].v], dis[p[j].u] + p[j].t);
    int flag = 0;
    for(int i = 1; i <= 2 * m + w; i++)
        if(dis[p[i].v] > dis[p[i].u] + p[i].t){
            flag = 1;
            break;
        }
    if(flag) cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main(){
    int f;
    cin >> f;
    while(f--){
        cin >> n >> m >> w;
        for(int i = 1; i <= 2 * m - 1; i += 2){
            cin >> p[i].u >> p[i].v >> p[i].t;
            p[i + 1].v = p[i].u;
            p[i + 1].u = p[i].v;
            p[i + 1].t = p[i].t;
        }
        for(int i = 2 * m + 1; i <= 2 * m + w; i++){
            cin >> p[i].u >> p[i].v >> p[i].t;
            p[i].t = -p[i].t;
        }
        Bellman_Ford();
    }
    return 0;
}

/*
Input:
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
Output:
NO
YES
*/