最短路-Spfa 配题（HDU 3790）

本文主要是介绍最短路-Spfa 配题（HDU 3790），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Spfa最短路算法，属于单源最短路，可以存在负权边，可以判断负环。

Spfa的算法思想从源点层层松弛，达到全图的单源最短。

题目：HDU 3790（题意很简单）

注意：输入边的信息的时候，用scanf，别用cin，会超时。

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<cstdio>
using namespace std;
const int max_n = 1001;
const int INF = 10000000;
int n, m;struct NODE
{int v;int w;int p;
};
vector<NODE>graph[max_n];void Spfa(int source, int sink)
{queue<int>Q;bool vis[max_n];int dis[max_n];int price[max_n];while (!Q.empty()) Q.pop();memset(vis, false, sizeof(vis));for (int i = 1; i <= n; i++){dis[i] = INF;}dis[source] = 0;price[source] = 0;vis[source] = true;Q.push(source);while (!Q.empty()){int cur_node = Q.front();Q.pop();vis[cur_node] = false;for (int i 

这篇关于最短路-Spfa 配题（HDU 3790）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---