poj1511 最短路 spfa

//
poj1511 最短路 spfa
//
//
Bellman-Ford 队列优化
//
//
留个spfa模板，精髓就是不断松弛，并将可能会影响
//
结果的点，如果在队列中不用加，不在就加入。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
typedef long long ll;
using namespace std;
const int MAX_N = 1000009;
const int INF = 0x7f7f7f7f;
//typedef pair<int,int> P;
int head[MAX_N];
int num;
int n,m;
bool inq[MAX_N];
ll d[MAX_N];
int cnt[MAX_N];
struct edge{
int from;
int to;
int w;
edge(){}
edge(int from,int to,int w):from(from),to(to),w(w){}
};
edge eg[MAX_N];
struct node {
int to;
int w;
int next;
node(){
}
node(int to,int w,int next):to(to),w(w),next(next){
}
};
node edges[MAX_N];
queue<int> que;
void add_edge(int u,int v,int cost){
edges[num] = node(v,cost,head[u]);
head[u] = num++;
}
void input(){
scanf("%d%d",&n,&m);
int u,v,w;
for (int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
eg[i] = edge(u,v,w);
}
}
void graph(){
memset(head,-1,sizeof(head));
num = 0;
for (int i=1;i<=m;i++){
add_edge(eg[i].from,eg[i].to,eg[i].w);
}
}
void reverser(){
for (int i=1;i<=m;i++){
swap(eg[i].from,eg[i].to);
}
}
ll spfa(int s){
memset(inq,0,sizeof(inq));
for (int i=1;i<=n;i++)
d[i] = INF;
memset(cnt,0,sizeof(cnt));
d[s] = 0;
que.push(s);
cnt[s]++;
inq[s] = true;
while(!que.empty()){
int
u = que.front();
que.pop();
for (int j = head[u];j!=-1;j=edges[j].next){
int v = edges[j].to;
int w = edges[j].w;
if (d[u] != INF && d[v] > d[u] + w){
d[v] = d[u] + w;
if (!inq[v]){
que.push(v);
cnt[v]++;
if (cnt[v]>=n){
return -1;
}
inq[v] = true;
}
}
}
inq[u] = false;
}
ll res = 0;
for (int i=1;i<=n;i++){
res += d[i];
}
return res;
}
void solve(){
graph();
ll cost = spfa(1);
reverser();
graph();
cost += spfa(1);
printf("%lldn",cost);
}
int main(){
int t;
//freopen("1.txt","r",stdin);
scanf("%d",&t);
while(t--){
input();
solve();
}
}

最后

以上就是外向香烟为你收集整理的poj1511 最短路 spfa的全部内容，希望文章能够帮你解决poj1511 最短路 spfa所遇到的程序开发问题。

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