本文主要是介绍poj 1511 Invitation Cards(spfa最短路)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意是给你点与点之间的距离，求来回到点1的最短路中的边权和。
因为边很大，不能用原来的dijkstra什么的，所以用spfa来做。并且注意要用long long int 来存储。
稍微改了一下学长的模板。
stack stl 实现代码：
#include<stdio.h>
#include<stack>
using namespace std;
const int MaxN = 1000001;
const int INF = 0x3f3f3f3f;int head[MaxN];
int outnum[MaxN];
bool vis[MaxN];
int n, m, num_edge;
long long int dis[MaxN];struct edge
{int from, to, len;
} e[MaxN];struct node
{int nfrom, nto, nlen;
} no[MaxN];void addedge(int f, int t, int l)
{e[num_edge].from = head[f];e[num_edge].to = t;e[num_edge].len = l;head[f] = num_edge++;
}bool spfa()
{for(int i = 1; i <= n; i++){dis[i] = INF;outnum[i] = 0;vis[i] = false;}stack<int>s;s.push(1);vis[1] = true;dis[1] = 0;while(!s.empty()){int cur = s.top();s.pop();outnum[cur]++;if(outnum[cur] > n){return false;}for(int i = head[cur]; i != -1; i = e[i].from){int x = e[i].to;if(dis[x] > dis[cur] + e[i].len){dis[x] = dis[cur] + e[i].len;if(!vis[x]){vis[x] = true;s.push(x);}}}vis[cur] = false;}return true;
}int main()
{int ncase;scanf("%d", &ncase);while(ncase--){scanf("%d%d", &n, &m);num_edge = 0;for(int i = 0; i <= n; i++){head[i] = -1;}for(int i = 0; i < m; i++){scanf("%d%d%d", &no[i].nfrom, &no[i].nto, &no[i].nlen);addedge(no[i].nfrom, no[i].nto, no[i].nlen);}long long int ans = 0;spfa();for(int i = 1; i <= n; i++){ans += dis[i];}num_edge = 0;for(int i = 0; i <= n; i++){head[i] = -1;}for(int i = 0; i < m; i++){addedge(no[i].nto, no[i].nfrom, no[i].nlen);}spfa();for(int i = 1; i <= n; i++){ans += dis[i];}printf("%lld\n", ans);}return 0;
}
结果，（44204K，1891MS），好像没差多少，还错了一发。
数组模拟栈spfa代码：
#include<stdio.h>#include<stack>using namespace std;const int MaxN = 1000001;const int INF = 0x3f3f3f3f;int head[MaxN];int outnum[MaxN];bool vis[MaxN];int n, m, num_edge;long long int dis[MaxN];struct edge{int from, to, len;} e[MaxN];struct node{int nfrom, nto, nlen;} no[MaxN];void addedge(int f, int t, int l){e[num_edge].from = head[f];e[num_edge].to = t;e[num_edge].len = l;head[f] = num_edge++;}int s[MaxN];bool spfa(){int top;for(int i = 1; i <= n; i++){s[i] = 0;//debug 重新初始化dis[i] = INF;outnum[i] = 0;vis[i] = false;}dis[1] = 0;s[0] = 1;top = 1;vis[1] = true;while(top){int cur = s[--top];outnum[cur]++;if(outnum[cur] > n){return false;}for(int i = head[cur] ; i != -1 ; i = e[i].from){int x = e[i].to;if(dis[x] > dis[cur] + e[i].len){dis[x] = dis[cur] + e[i].len;if(!vis[x]){s[top++] = x;vis[x] = true;}}}vis[cur] = false;}return true;}int main(){int ncase;scanf("%d", &ncase);while(ncase--){scanf("%d%d", &n, &m);num_edge = 0;for(int i = 0; i <= n; i++){head[i] = -1;}for(int i = 0; i < m; i++){scanf("%d%d%d", &no[i].nfrom, &no[i].nto, &no[i].nlen);addedge(no[i].nfrom, no[i].nto, no[i].nlen);}long long int ans = 0;spfa();for(int i = 1; i <= n; i++){ans += dis[i];}num_edge = 0;for(int i = 0; i <= n; i++){head[i] = -1;}for(int i = 0; i < m; i++){addedge(no[i].nto, no[i].nfrom, no[i].nlen);}spfa();for(int i = 1; i <= n; i++){ans += dis[i];}printf("%lld\n", ans);}return 0;}这篇关于poj 1511 Invitation Cards(spfa最短路)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
