题目：http://vj.acmclub.cn/contest/view.action?cid=316#problem/E

 

首先要理解题意：其实就是给你一个图让你判断有没有负权回路

 

因此直接用BallmenFord算法就可以了

 

特别注意一些问题：path是双向的因此要写两遍

 

代码：

# include
     
      //# include
      
       # include
       
        using namespace std;const int INF = 99999999;const int MAXN = 5500;int u[MAXN], v[MAXN], w[MAXN];int N, M, W, k;int dis[550];bool bellman_ford(){    bool check = 0;    memset(dis, INF, sizeof(dis));    dis[1] = 0;    for (int i = 0; i < N - 1; i++)    {        check = 1;        for (int j = 1; j < k; j++)        {            if (dis[u[j]]
        
          dis[u[j]] + w[j])            {                check = 0;                dis[v[j]] = dis[u[j]] + w[j];            }        }        if (check)            return false;    }    for (int i = 1; i 
         
           dis[u[i]] + w[i])            return true;    return false;}int main(){    int F, s, e, t;    cin >> F;    while (F--)    {        k = 1;        cin >> N >> M >> W;        for (int i = 1; i <= M; i++)        {            cin >> s >> e >> t;            u[k] = s;            v[k] = e;            w[k] = t;            k++;            u[k] = e;            v[k] = s;            w[k] = t;            k++;        }        for (int i = 1; i <= W; i++)        {            cin >> s >> e >> t;            u[k] = s;            v[k] = e;            w[k] = -t;            k++;        }        if (bellman_ford())            cout << "YES" << endl;        else            cout << "NO" << endl;    }    //system("pause");    return 0;}
         
        
       
      
     

本来是想用一下SPFA的，尝试了一下队列+vector的操作，结果WA了

对vector的用法可能还不不是太熟悉，另外SPFA也没太理解，尤其是用SPFA判断负权回路很麻烦

待我再研究