spfa 判断负环

简介: 笔记

SPFA判断负环


基本过程与spfa求最短路相同,但是额外记录一个 cnt数组,表示到当前点的最短路经过的边的条数,如果cnt[i]>=n说明一定存在一个负环。

此外,初始化队列的时候,要将所有点都加入队列,因为1可能到不了负环存在的位置。

#include<bits/stdc++.h>
#include<unordered_map>
// #define int long long
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
#define debug(x,y) cerr << (x) << " == " << (y) << endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
//template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; }
const int N = 1e5 + 10;
int n, m;
vector<PII>vec[N];
int d[N], cnt[N];
bool vis[N];
bool spfa() {
    queue<int>q;
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    vis[1] = true;
    for (int i = 1; i <= n; ++i)q.push(i);
    while (q.size()) {
        int t = q.front();
        q.pop();
        vis[t] = false;
        for (int i = 0; i < vec[t].size(); ++i) {
            int j = vec[t][i].second;
            int dis = vec[t][i].first;
            if (d[j] > d[t] + dis) {
                d[j] = d[t] + dis;
                if (!vis[j])q.push(j);
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n)return true;
            }
        }
    }
    return false;
}
void solve() {
    cin >> n >> m;
    while (m--) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        vec[u].push_back({ w,v });
    }
    if (spfa())puts("Yes");
    else puts("No");
}
signed main() {
    // int _; cin >> _;
    // while (_--)
        solve();
    return 0;
}
目录
打赏
0
0
0
0
1
分享
相关文章
深度评测 | 仅用3分钟,百炼调用满血版 Deepseek-r1 API,百万Token免费用,简直不要太爽。
仅用3分钟,百炼调用满血版Deepseek-r1 API,享受百万免费Token。阿里云提供零门槛、快速部署的解决方案,支持云控制台和Cloud Shell两种方式,操作简便。Deepseek-r1满血版在推理能力上表现出色,尤其擅长数学、代码和自然语言处理任务,使用过程中无卡顿,体验丝滑。结合Chatbox工具,用户可轻松掌控模型,提升工作效率。阿里云大模型服务平台百炼不仅速度快,还确保数据安全,值得信赖。
189461 32
深度评测 | 仅用3分钟,百炼调用满血版 Deepseek-r1 API,百万Token免费用,简直不要太爽。
用DeepSeek,就在阿里云!四种方式助您快速使用 DeepSeek-R1 满血版!更有内部实战指导!
DeepSeek自发布以来,凭借卓越的技术性能和开源策略迅速吸引了全球关注。DeepSeek-R1作为系列中的佼佼者,在多个基准测试中超越现有顶尖模型,展现了强大的推理能力。然而,由于其爆火及受到黑客攻击,官网使用受限,影响用户体验。为解决这一问题,阿里云提供了多种解决方案。
23684 37
PAI Model Gallery 支持云上一键部署 DeepSeek-V3、DeepSeek-R1 系列模型
DeepSeek 系列模型以其卓越性能在全球范围内备受瞩目,多次评测中表现优异,性能接近甚至超越国际顶尖闭源模型(如OpenAI的GPT-4、Claude-3.5-Sonnet等)。企业用户和开发者可使用 PAI 平台一键部署 DeepSeek 系列模型,实现 DeepSeek 系列模型与现有业务的高效融合。
零门槛,轻松体验阿里云 DeepSeek-R1 满血版:快速部署,立享超强推理能力
DeepSeek-R1 是阿里云推出的先进推理模型,专为解决复杂任务设计,尤其在数学推理、代码生成与修复、自然语言处理等领域表现出色。通过阿里云的“零门槛”解决方案,用户无需编写代码即可快速部署 DeepSeek-R1,大幅简化了部署流程并提升了使用效率。该方案提供了详尽的文档和可视化界面,使开发者能轻松上手。DeepSeek-R1 支持多种模型尺寸,适用于不同场景,如智能客服、代码自动化生成、数学问题求解和跨领域知识推理。尽管存在对高自定义需求支持有限、云端依赖性等不足,但对于希望快速验证模型效果的用户而言,阿里云的这一解决方案仍然是高效且经济的选择。
1894 29
零门槛、百万token免费用,即刻拥有DeepSeek-R1满血版,还有实践落地调用场景等你来看
DeepSeek 是热门的推理模型,能在少量标注数据下显著提升推理能力,尤其擅长数学、代码和自然语言等复杂任务。本文涵盖四种部署方案,可以让你快速体验云上调用 DeepSeek-R1 满血版的 API 及部署各尺寸模型的方式,无需编码,最快 5 分钟、最低 0 元即可实现
本地部署DeepSeek模型
要在本地部署DeepSeek模型,需准备Linux(推荐Ubuntu 20.04+)或兼容的Windows/macOS环境,配备NVIDIA GPU(建议RTX 3060+)。安装Python 3.8+、PyTorch/TensorFlow等依赖,并通过官方渠道下载模型文件。配置模型后,编写推理脚本进行测试,可选使用FastAPI服务化部署或Docker容器化。注意资源监控和许可协议。
1663 10
DeepSeek-R1满血版上线阿里云,新用户专享100万token额度,5分钟快速部署!
DeepSeek是当前AI领域的热门话题,尤其其大模型备受关注。由于网页版访问时常超时,推荐使用阿里云百炼的API调用方式快速体验。此方法仅需五分钟,提供100万免费Token,有效期至2025年7月26日。用户可通过注册阿里云账户、开通服务、创建API-Key、安装并配置ChatBox客户端等步骤轻松上手。测试结果显示,DeepSeek-R1在回答问题、解释数学概念及编写代码等方面表现优异。部署成本低、操作简便,是体验DeepSeek的理想选择。
DeepSeek-R1满血版上线阿里云,新用户专享100万token额度,5分钟快速部署!
手把手教你使用 Ollama 和 LobeChat 快速本地部署 DeepSeek R1 模型,创建个性化 AI 助手
DeepSeek R1 + LobeChat + Ollama:快速本地部署模型,创建个性化 AI 助手
3578 117
手把手教你使用 Ollama 和 LobeChat 快速本地部署 DeepSeek R1 模型,创建个性化 AI 助手
如何在通义灵码里用上DeepSeek-V3 和 DeepSeek-R1 满血版671B模型?
除了 AI 程序员的重磅上线外,近期通义灵码能力再升级全新上线模型选择功能,目前已经支持 Qwen2.5、DeepSeek-V3 和 R1系列模型,用户可以在 VSCode 和 JetBrains 里搜索并下载最新通义灵码插件,在输入框里选择模型,即可轻松切换模型。
1168 14
满血 DeepSeek 免费用?附联网搜索&prompt编写教程!暨第三方 API 平台全面横评
满血 DeepSeek 免费用!支持联网搜索!创作声明:真人攥写-非AI生成,Written-By-Human-Not-By-AI
1240 8
满血 DeepSeek 免费用?附联网搜索&prompt编写教程!暨第三方 API 平台全面横评

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等