POJ

POJ - 3259 题目链接
这是一道检查是否有负权边的最短路问题
一开始不知道怎么分析的，好像能选取一个点进行两遍Dijkstra，然后显然的wa了，
然后仔细分析了一波，这是一个多源路径形成回路的问题，之前在洛谷做过类似问题，
而且这道题目数据量只有500，那就不是可以用Floyed了，这道题也确实是Floyed,
我们考虑建边，正常的边权是正的，虫洞的边权，我们建成负的。
然后跑一边Floyed，然后简单的TLE了。
理性分析一波，不应该啊，最大耗时也就是也就是500 * 500 * 500 * 5，而且不可能达到这个最大值啊
思路是没错的，接着改，一开始我在加边的时候用的是min函数来加上最优边，跑Floyed的时候也是用min函数来判断的，
果断换成if语句来判断，交一发，终于看的了Accepted。

//Powered by CK
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e3 + 10;
int ans[N][N], n, m, l;
void init() {
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i == j)  ans[i][j] = 0;
            else    ans[i][j] = INF;
}
string Floyed() {
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++)
                if(ans[i][j] > ans[i][k] + ans[k][j])//if
                    ans[i][j] = ans[i][k] + ans[k][j];
            if(ans[i][i] < 0)   return "YES";//如果我的推理没错的话，一定是在这重循环判断是否重边，最外面的k是中转点，j是目标点，i是起点，所以应该是判断起点回到起点。
        }
    }
    return "NO";
}
int main() {
    // freopen("in.txt", "r", stdin);
    int t, x, y, w;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d %d", &n, &m, &l);
        init();
        for(int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &w);
            if(w < ans[x][y])//还是老老实实用if把
                ans[y][x] = ans[x][y] = w;
        }
        for(int i = 0; i < l; i++) {
            scanf("%d %d %d", &x, &y, &w);
            ans[x][y] = -w;
        }
        cout << Floyed() << endl;;
    }
    return 0;
}