本文主要是介绍HDU 1535 Invitation Cards （spfa， 链式前向星，逆向建图），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
hdu 1535
题意就是先算出从点1到其他点的最短路径长度，然后算出从其他各点到1的最短路径，最后求和。
算从其他各点到1的最短路径时应该先将图逆向存储，此时spfa算法也有差异，详见代码。
参考博客：http://blog.csdn.net/libin56842/article/details/17102133
第一次学会链式前向星。。。感谢http://blog.csdn.net/acdreamers/article/details/16902023
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstring>
#define inf 0x7fffffff
using namespace std;
const int MAXN = 1000010;
int N, M;
struct edge {int from;int to;int w;
};
edge edges[MAXN];
int First[MAXN], Next[MAXN];
int dis[MAXN], vis[MAXN];
void spfa(int src, int flag) {int i;for(i = 1; i <= N; i++) {dis[i] = inf;}dis[src] = 0;for(i = 1; i <= N; i++) {vis[i] = 0;}queue<int> Q;Q.push(src);while(!Q.empty()) {src = Q.front();Q.pop();vis[src] = 0;for(i = First[src]; i != -1; i = Next[i]) {int to = (flag ? edges[i].to : edges[i].from);if(dis[to] > dis[src] + edges[i].w) {dis[to] = dis[src] + edges[i].w;if(!vis[to]) {vis[to] = 1;Q.push(to);}}}}
}
int main() {int n;while(~scanf("%d", &n) && n) {while(n--) {scanf("%d %d", &N, &M);int i;for(i = 0; i < M; i++) {First[i] = Next[i] = -1;}for(i = 0; i < M; i++ ) {scanf("%d %d %d", &edges[i].from, &edges[i].to, &edges[i].w);Next[i] = First[edges[i].from];First[edges[i].from] = i;}spfa(1, 1);int cost = 0;for(i = 1; i <= N; i++) {cost += dis[i];}for(i = 0; i <= M; i++) { //将图重置 First[i] = Next[i] = -1;}for(i = 0; i < M; i++) {Next[i] = First[edges[i].to];First[edges[i].to] = i;}spfa(1, 0);for(i = 1; i <= N; i++) {cost += dis[i];}printf("%d\n", cost);}}return 0;
}
这篇关于HDU 1535 Invitation Cards （spfa， 链式前向星，逆向建图）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
