题目：
2 2 2 1 2 13 2 1 33 4 6 1 2 10 2 1 60 1 3 20 3 4 10 2 4 5 4 1 50
46 210
题目分析：
这道题采用spfa来做。有以下2中思路：
1）首先以1为源点进行一次spfa()算法，求得1到2~n点的最短距离。接下来就是分别以2~n点位源点，进行spfa()，这样既可得到答案。但是这就得进行n次spfa()算法了，在这种数据规模下(节点数n最大可达1000000)，很有可能会TLE。
2）反向建边。首先以1位源点进行一次spfa算法(),求得1到2~n各个节点的最短距离。然后反向建边，再以1位源点进行一次spfa()算法，这时其实求得的是2~n到1的最短距离。(这道题是有向图，不是无向图)。
以下分别贴上了自己写的三个版本，虽然后面两个这道题没能AC。但是基本体现了用各种数据结构实现的spfa算法的
基本思路及基本使用。
AC代码如下(spfa，用队列+邻接表的实现)：
代码如下：
/*
* hdu_1535_1.cpp
*
* Created on: 2015年3月27日
* Author: Administrator
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int SIZE = 1000001;
const int INF = 0x3f3f3f3f;
int u[2 * SIZE], v[2 * SIZE], w[2 * SIZE], nextt[2 * SIZE];
int startss[2 * SIZE], endss[2 * SIZE], weightss[2 * SIZE];
int head[SIZE], dist[SIZE];
int n, m, cnt;
/**
* 初始化
*/
void init() {
memset(u, 0, sizeof(u));
memset(v, 0, sizeof(v));
memset(w, INF, sizeof(w));
memset(dist, 0, sizeof(dist));
memset(nextt, 0, sizeof(nextt));
memset(head, -1, sizeof(head));
cnt = 0;
}
/**
* 用队列实现的spfa。
*
* 参数说明:
* src: 起点(源点)
*/
void spfa(int src) {
queue<int> q;
bool inq[SIZE] = { 0 };
for (int i = 1; i <= n; i++)
dist[i] = (i == src) ? 0 : INF;
q.push(src);
while (!q.empty()) {
int x = q.front();
q.pop();
inq[x] = 0;
for (int e = head[x]; e != -1; e = nextt[e])
if (dist[v[e]] > dist[x] + w[e]) {
dist[v[e]] = dist[x] + w[e];
if (!inq[v[e]]) {
inq[v[e]] = 1;
q.push(v[e]);
}
}
}
}
/**
* 添加边
*/
void add_edge(int u1, int v1, int w1) {
u[cnt] = u1;
v[cnt] = v1;
w[cnt] = w1;
nextt[cnt] = head[u[cnt]];
head[u[cnt]] = cnt;
cnt++;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
int i;
for (i = 0; i < m; ++i) {
scanf("%d%d%d", &startss[i], &endss[i], &weightss[i]);
}
/**
* 使用spfa算法的基本步骤
*/
init();//初始化
for (i = 0; i < m; ++i) {//读入数据
add_edge(startss[i], endss[i], weightss[i]);
}
spfa(1);//进行运算
int ans = 0;
for(i = 2 ; i <= n ; ++i){//计算1到各个节点的最短距离
ans += dist[i];
}
init();
for(i = 0 ; i < m ; ++i){//这里反向建边
add_edge(endss[i],startss[i],weightss[i]);
}
spfa(1);
for(i = 2 ; i <= n ; ++i){//计算回程时各个节点到1的最短距离
ans += dist[i];
}
printf("%d\n",ans);//输出最后的结果..
}
return 0;
}
StackOverFlow的版本：
spfa(用栈+邻接表)
/*
* hdu_1535.cpp
*
* Created on: 2015年3月27日
* Author: Administrator
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x3F3F3F3F;
const int V = 1000010;
const int E = 1000010;
int pnt[4*E], cost[4*E], nxt[4*E];
int e, head[V];
int dist[V];
bool vis[V];
int startss[4*E];
int endss[4*E];
int weightss[4*E];
int relax(int u, int v, int c) {
if (dist[v] > dist[u] + c) {
dist[v] = dist[u] + c;
return 1;
}
return 0;
}
inline void addedge(int u, int v, int c) {
pnt[e] = v;
cost[e] = c;
nxt[e] = head[u];
head[u] = e++;
}
/**
* 使用 邻接表+栈 实现的spfa
*
* 参数说明:
* src: 源点
* n: 节点的个数
*/
int SPFA(int src, int n) { // 此处用堆栈实现，有些时候比队列要快
int i;
for (i = 1; i <= n; ++i) { // 顶点1...n
vis[i] = 0;
dist[i] = INF;
}
dist[src] = 0;
int Q[E], top = 1;
Q[0] = src;
vis[src] = true;
while (top) {
int u, v;
u = Q[--top];
vis[u] = false;
for (i = head[u]; i != -1; i = nxt[i]) {
v = pnt[i];
if (1 == relax(u, v, cost[i]) && !vis[v]) {
Q[top++] = v;
vis[v] = true;
}
}
}
return dist[n];
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, m;
scanf("%d%d", &n, &m);
memset(head, -1, sizeof(head));
e = 0;
int i;
for (i = 0; i < m; ++i) {
scanf("%d%d%d", &startss[i], &endss[i], &weightss[i]);
}
for(i = 0 ; i < m ; ++i){
addedge(startss[i],endss[i],weightss[i]);
}
int ans = 0;
SPFA(1, n);
for (i = 2; i <= n; ++i) {
ans += dist[i];
}
memset(head, -1, sizeof(head));
e = 0;
for(i = 0 ; i < m ; ++i){
addedge(endss[i],startss[i],weightss[i]);
}
SPFA(1,n);
for(i = 2 ; i <= n ; ++i){
ans += dist[i];
}
printf("%d\n",ans);
}
return 0;
}
CE的版本：
spfa算法(队列+邻接矩阵)
CE的原因估计是：二位矩阵开得太大了。
/*
* hdu1535.cpp
*
* Created on: 2015年3月27日
* Author: Administrator
*/
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1000001;
const int INF = 0x3f3f3f3f;
int map[N][N], dist[N];
bool visit[N];
int n, m;
int startss[N];
int endss[N];
int weightss[N];
void init() {//初始化
int i, j;
for (i = 1; i < N; i++) {
for (j = 1; j < N; j++) {
if (i == j) {
map[i][j] = 0;
} else {
map[i][j] = map[j][i] = INF;
}
}
}
}
/**
* SPFA算法.
* 使用spfa算法来求单元最短路径
* 参数说明:
* start:起点
*/
void spfa(int start) {
queue<int> Q;
int i, now;
memset(visit, false, sizeof(visit));
for (i = 1; i <= n; i++){
dist[i] = INF;
}
dist[start] = 0;
Q.push(start);
visit[start] = true;
while (!Q.empty()) {
now = Q.front();
Q.pop();
visit[now] = false;
for (i = 1; i <= n; i++) {
if (dist[i] > dist[now] + map[now][i]) {
dist[i] = dist[now] + map[now][i];
if (visit[i] == 0) {
Q.push(i);
visit[i] = true;
}
}
}
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
init();
int i;
for(i = 0 ; i < m ; ++i){
scanf("%d%d%d",&startss[i],&endss[i],&weightss[i]);
}
int ans = 0;
for(i = 0 ; i < m ; ++i){
map[startss[i]][endss[i]] = weightss[i];
}
spfa(1);
for(i = 2 ; i <= n ; ++i){
ans += dist[i];
}
init();
for(i = 0 ; i < m ; ++i){
map[endss[i]][startss[i]] = weightss[i];
}
spfa(1);
for(i = 2 ; i <= n ; ++i){
ans += dist[i];
}
printf("%d\n",ans);
}
return 0;
}
(spfa专题 1.1)hdu 1535 Invitation Cards(求从1到2~n的点后，再从2~n返回1点的最小距离)
原文：http://blog.csdn.net/hjd_love_zzt/article/details/44672875