poj1797 spfa 最短路

题目链接：点击打开链接

题意：

给一个无向图，每条边有个能承受的重量；

问从1到n的最大通过的重量；

理解：

这是以前比赛的一个题；

当时用的多个最短路，最后超时；

实际上在最短路的递推式上改一下就行了；

d[v] = max(d[v], min(d[u], w[u, v]));

实际上跟求最短路是一样的；

刚学的spfa用上去很好；

实际上它用队列只维护了每个点；

而对于前向星存图也很有趣；

用起来都很不错；

代码如下：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;
const int INF = 0x7fffffff;
const int N = 10000000;
typedef pair<int, int> PII;
#define X first
#define Y second
const int MAXE = MAXN;
const int MAXV = 1011;
struct node {
int to, next, cost;
}e[MAXE];
int head[MAXV], tot;
int n, m;
void init() {
memset(head, -1, sizeof head);
tot = 0;
}
void add_edge(int u, int v, int cost) {
e[tot].to = v;
e[tot].next = head[u];
e[tot].cost = cost;
head[u] = tot++;
}
int dis[MAXV];
int outque[MAXV];
bool vis[MAXV];
bool spfa(int s) {
for (int i = 1; i <= n; ++i) {
vis[i] = false;
dis[i] = -1;
outque[i] = 0;
}
queue<int> que;
que.push(s);
dis[s] = INF;
vis[s] = true;
while (!que.empty()) {
int u = que.front();
que.pop();
vis[u] = false;
if (++outque[u] > n) {
return false;
}
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].to;
int cost = min(dis[u], e[i].cost);
if (dis[v] >= cost) {
continue;
}
dis[v] = cost;
if (vis[v] == true) {
continue;
}
vis[v] = true;
que.push(v);
}
}
return true;
}
int main() {
int t;
cin >> t;
for (int I = 1; I <= t; ++I) {
cin >> n >> m;
init();
for (int i = 0; i < m; ++i) {
int u, v, cost;
scanf("%d%d%d", &u, &v, &cost);
add_edge(u, v, cost);
add_edge(v, u, cost);
}
spfa(1);
cout << "Scenario #" << I << ":" << endl;
cout << dis[n] << endl;
cout << endl;
}
return 0;
}

最后

以上就是安详大树为你收集整理的poj1797 spfa 最短路的全部内容，希望文章能够帮你解决poj1797 spfa 最短路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。