题目大意
N个点，M条双向路径，W条单向路径。从双向路径的一端到另一端所花费时间为正值，从单向路径的源点到终点所花时间为负值。问是否存在一条从A出发，再回到A的回路，满足回到A的时间小于出发时间。
题目分析
显然为一个求含负权边的图中是否含有负权和回路。采用SPFA算法解决。
实现(c++)
#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
#define MAX_NODE 505
#define INFINITE 1 << 30
struct Edge{
int vertex;
int dist;
Edge(int v, int d) :
vertex(v), dist(d){};
}; vector<vector<Edge> > gGraph; int gDist[MAX_NODE];
int gUpdateTime[MAX_NODE]; //记录原点到每个点的最短路径被更新的次数，根据SPFA算法，若更新次数>n,则说明存在负环
bool Spfa(int s, int d, int n){
queue<int> Q; Q.push(s); memset(gUpdateTime, 0, sizeof(gUpdateTime)); //每个点被更新次数
for (int i = 1; i <= n; i++) //初始化原点到每个点的距离
gDist[i] = INFINITE;
gDist[s] = 0; while (!Q.empty()){
//SPFA算法，使用一个先进先出队列。按照广度优先，每增加一层的深度，到达当前深度k。就可以确定
//从原点开始到达该点的最短路径为k步的点。
int v = Q.front();
Q.pop();
for (int i = 0; i < gGraph[v].size(); i++){
if (gDist[gGraph[v][i].vertex] > gDist[v] + gGraph[v][i].dist){
gDist[gGraph[v][i].vertex] = gDist[v] + gGraph[v][i].dist;
if (++gUpdateTime[gGraph[v][i].vertex] >= n){ //存在负权和环
return false;
}
Q.push(gGraph[v][i].vertex);
}
}
} return true; //不存在负权和环
}
int main(){
int f;
scanf("%d", &f);
while (f--){
int n, m, w, s, e, t;
scanf("%d %d %d", &n, &m, &w);
gGraph.clear();
gGraph.resize(n + 1);
for (int i = 0; i < m; i++){
scanf("%d %d %d", &s, &e, &t);
gGraph[s].push_back(Edge(e, t));
gGraph[e].push_back(Edge(s, t));
}
for (int i = 0; i < w; i++){
scanf("%d %d %d", &s, &e, &t);
gGraph[s].push_back(Edge(e, -t));
}
if (Spfa(1, n, n)){
printf("NO\n");
}
else
printf("YES\n");
}
return 0;
}