题解 P3385 【【模板】负环】
kion
2018-08-22 13:38:43
## **SPjkstra算法**
SPjkstra算法，~~顾名思义就是SPFA与Dijkstra算法重重叠加~~，效果良好。
SPjkstra算法：193ms
SPFA算法：13266ms
说明：为第一个测试点的测试数据。
什么是SPjkstra算法？
就是某些蒟蒻~~比如说我~~因为只学了SPFA算法，但是发现程序运行太慢了，**直接将SPFA中的队列换成优先队列**的~~偷懒~~做法。
```c
// P3385.cpp: 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <list>
#include <memory.h>
using namespace std;
int n, m;
const int maxn = 20005;
struct edge
{
int to, w;
edge()
{
to = 0;
w = 0;
}
edge(int a, int b)
{
to = a;
w = b;
}
};
vector< vector<edge> > G;
int d[maxn];
const int INF = 1 << 30;
int cnt[maxn];
bool flag = 1;
bool v[maxn];
inline int read()
{
bool minus = 0;
int x = 0; char c = getchar();
for (; !isdigit(c); c = getchar())
if (c == '-')minus = 1;
for (; isdigit(c); c = getchar())
x = x * 10 + c - '0';
if (minus)return -x;
return x;
}
inline void intial()//初始化函数
{
G.clear();
memset(v, 0, sizeof(v));
for (int i = 0; i < maxn; i++)
d[i] = INF;
memset(cnt, 0, sizeof(cnt));
}
struct node//只是为了重载符号
{
int x;
node(int a)
{
x = a;
}
bool operator <(const node& i)const
{
return this->x > i.x;
}
};
void SPijkstra(int start)//本来是SPFA
{
priority_queue<node> Q;
//queue<node> Q;
Q.push(node(start));
v[start] = 1;
d[start] = 0;
cnt[start] = 1;
while (!Q.empty())
{
int x = Q.top().x;
Q.pop();
v[x] = 0;
for (int i = 0; i < G[x].size(); i++)
{
int t = G[x][i].to, w = G[x][i].w;
if (d[x] + w < d[t])
{
d[t] = d[x] + w;
cnt[t] = cnt[x] + 1;
if (!v[t])
{
if (cnt[t] > n)//BFS深度超过n == 存在负环
{
flag = 0;
return;
}
v[t] = 1;
Q.push(node(t));
}
}
}
}
}
int main()
{
freopen("C:\\Users\\Administrator\\Downloads\\testdata (16).in", "r", stdin);
int oo;
oo = read();
for (int pp = 1; pp <= oo; pp++)
{
flag = 1;
intial();
n = read();
m = read();
vector<edge>samp;
G.assign(n + 10, samp);
for (int i = 1; i <= m; i++)
{
int a, b, w;
a = read();
b = read();
w = read();
if (w < 0)
{
G[a].push_back(edge(b, w));
}
else
{
G[a].push_back(edge(b, w));
G[b].push_back(edge(a, w));
}
}
SPijkstra(1);
if (flag == 0)
cout << "YE5" << endl;
if (flag)
cout << "N0" << endl;
}
return 0;
}
```