首页 > 代码库 > HDU 1535 Invitation Cards (最短路，附SLF优化SPFA)
HDU 1535 Invitation Cards (最短路，附SLF优化SPFA)
题目：
http://acm.hdu.edu.cn/showproblem.php?pid=1535
题意：
有向图，求点1到点2-n的最短距离之和以及点2-n到点1的最短距离之和
方法：
1、跑1为原点的最短路
2、反向建图(把有向图的边反向，(u,v,w)变成(v,u,w))，跑1为原点的最短路
3、将两者距离之和加和即可（注意用 long long ，int会溢出）
1 void input() 2 { 3 scanf("%d%d", &n, &m); 4 g1.init(n); 5 g2.init(n); 6 for (int i = 0; i < m; i++) 7 { 8 int u, v, w; 9 scanf("%d%d%d", &u, &v, &w);10 g1.addse(u, v, w);11 g2.addse(v, u, w);12 }13 }14 void solve()15 {16 g1.spfa(1);17 g2.spfa(1);18 LL ans = 0;19 for (int i = 1; i <= n; i++)20 ans += g1.d[i], ans += g2.d[i];21 printf("%I64d\n", ans);22 }
加SLF优化的SPFA：
设队列队首元素为x，目前元素为v，若d[v]<d[x]则将v插入队列首，否则插入队列尾
1 /** 2 *含负权值加权图的单源最短路径：Spfa 算法(稀疏图)(O(KE))(不适用分层图)(SLF优化的SPFA) 3 *输入：图(链式前向星),n(顶点数,从1到n) 4 *输出：d[](距离) 5 */ 6 const int maxn = 0; 7 const int maxm = 0; 8 struct Edge 9 {10 int u, v, w;11 int next;12 } edge[maxm];13 int head[maxn], en;14 int n, m;15 int d[maxn];16 int pre[maxn];//用于解析路径17 int cnt[maxn];18 bool mark[maxn];19 deque<int> Q;20 void addse(int u, int v, int w)21 {22 edge[en].u = u;23 edge[en].v = v;24 edge[en].w = w;25 edge[en].next = head[u];26 head[u] = en++;27 }28 void init()29 {30 memset(head, -1, sizeof(head));31 en = 0;32 }33 /*DFS找负环34 bool cir[maxn];35 void dfs(int u)36 {37 cir[u]=true;38 for(int i=head[u]; i!=-1; i=edge[i].next)39 if(!cir[edge[i].v]) dfs(edge[i].v);40 }41 */42 bool spfa(int s)43 {44 memset(d, 0x3f, sizeof(int) * (n + 1));45 for (int i = 1; i <= n; ++i) pre[i] = i; //用于解析路径46 memset(mark, 0, sizeof(bool) * (n + 1));47 memset(cnt, 0, sizeof(int) * (n + 1));48 d[s] = 0;49 Q.push_back(s);50 mark[s] = 1;51 cnt[s]++;52 while (Q.size())53 {54 int u = Q.front();55 Q.pop_front();56 mark[u] = 0;57 for (int i = head[u]; i != -1; i = edge[i].next)58 {59 int v = edge[i].v;60 int w = edge[i].w;61 if (d[u] + w < d[v])62 {63 pre[v] = u; // 用于解析路径64 d[v] = d[u] + w;65 if (mark[v] == 0)66 {67 mark[v] = 1;68 if (!Q.empty())69 {70 if (d[v] > d[Q.front()]) Q.push_back(v);71 else Q.push_front(v);72 }73 else Q.push_back(v);74 if (++cnt[v] > n) return false; //有负环，可以用DFS找75 }76 }77 }78 }79 return true;80 }
代码：加SLF优化的SPFA最短路
1 /******************************************** 2 *ACM Solutions 3 * 4 *@Title: 5 *@Version: 1.0 6 *@Time: 2014-xx-xx 7 *@Solution: http://www.cnblogs.com/xysmlx/p/xxxxxxx.html 8 * 9 *@Author: xysmlx(Lingxiao Ma) 10 *@Blog: http://www.cnblogs.com/xysmlx 11 *@EMail: xysmlx@163.com 12 * 13 *Copyright (C) 2011-2015 xysmlx(Lingxiao Ma) 14 ********************************************/ 15 // #pragma comment(linker, "/STACK:102400000,102400000") 16 #include <cstdio> 17 #include <iostream> 18 #include <cstring> 19 #include <string> 20 #include <cmath> 21 #include <set> 22 #include <list> 23 #include <map> 24 #include <iterator> 25 #include <cstdlib> 26 #include <vector> 27 #include <queue> 28 #include <stack> 29 #include <algorithm> 30 #include <functional> 31 using namespace std; 32 typedef long long LL; 33 #define pb push_back 34 #define ROUND(x) round(x) 35 #define FLOOR(x) floor(x) 36 #define CEIL(x) ceil(x) 37 const int maxn = 1000010; 38 const int maxm = 2000010; 39 const int inf = 0x3f3f3f3f; 40 const LL inf64 = 0x3f3f3f3f3f3f3f3fLL; 41 const double INF = 1e30; 42 const double eps = 1e-6; 43 const int P[4] = {0, 0, -1, 1}; 44 const int Q[4] = {1, -1, 0, 0}; 45 const int PP[8] = { -1, -1, -1, 0, 0, 1, 1, 1}; 46 const int QQ[8] = { -1, 0, 1, -1, 1, -1, 0, 1}; 47 48 struct SPFA 49 { 50 struct Edge 51 { 52 int u, v, w; 53 int next; 54 } edge[maxm]; 55 int head[maxn], en; 56 int n, m; 57 int d[maxn]; 58 int cnt[maxn]; 59 int mark[maxn]; 60 deque<int> Q; 61 int pre[maxn];//用于解析路径 62 void addse(int u, int v, int w) 63 { 64 edge[en].u = u; 65 edge[en].v = v; 66 edge[en].w = w; 67 edge[en].next = head[u]; 68 head[u] = en++; 69 } 70 void init(int _n) 71 { 72 n = _n; 73 memset(head, -1, sizeof(head)); 74 en = 0; 75 while (!Q.empty()) Q.pop_back(); 76 } 77 78 /*DFS找负环 79 bool cir[maxn]; 80 void dfs(int u) 81 { 82 cir[u]=true; 83 for(int i=head[u]; i!=-1; i=edge[i].next) 84 if(!cir[edge[i].v]) dfs(edge[i].v); 85 } 86 */ 87 bool spfa(int s) 88 { 89 for (int i = 1; i <= n; ++i) d[i] = inf; 90 for (int i = 1; i <= n; ++i) pre[i] = i; //用于解析路径 91 memset(mark, 0, sizeof(mark)); 92 memset(cnt, 0, sizeof(cnt)); 93 d[s] = 0; 94 Q.push_back(s); 95 mark[s] = 1; 96 cnt[s]++; 97 while (Q.size()) 98 { 99 int u = Q.front();100 Q.pop_front();101 mark[u] = 0;102 for (int i = head[u]; i != -1; i = edge[i].next)103 {104 int v = edge[i].v;105 int w = edge[i].w;106 if (d[u] + w < d[v])107 {108 pre[v] = u; // 用于解析路径109 d[v] = d[u] + w;110 if (mark[v] == 0)111 {112 mark[v] = 1;113 if (!Q.empty())114 {115 if (d[v] > d[Q.front()]) Q.push_back(v);116 else Q.push_front(v);117 }118 else Q.push_back(v);119 if (++cnt[v] > n) return false; //有负环，可以用DFS找120 }121 }122 }123 }124 return true;125 }126 } g1, g2;127 128 int kase;129 int n, m;130 void init()131 {132 kase++;133 }134 void input()135 {136 scanf("%d%d", &n, &m);137 g1.init(n);138 g2.init(n);139 for (int i = 0; i < m; i++)140 {141 int u, v, w;142 scanf("%d%d%d", &u, &v, &w);143 g1.addse(u, v, w);144 g2.addse(v, u, w);145 }146 }147 void debug()148 {149 //150 }151 void solve()152 {153 g1.spfa(1);154 g2.spfa(1);155 LL ans = 0;156 for (int i = 1; i <= n; i++)157 ans += g1.d[i], ans += g2.d[i];158 printf("%I64d\n", ans);159 }160 void output()161 {162 //163 }164 int main()165 {166 // int size = 256 << 20; // 256MB167 // char *p = (char *)malloc(size) + size;168 // __asm__("movl %0, %%esp\n" :: "r"(p));169 170 // std::ios_base::sync_with_stdio(false);171 #ifdef xysmlx172 freopen("in.cpp", "r", stdin);173 #endif174 175 kase = 0;176 int T;177 scanf("%d", &T);178 while (T--)179 {180 init();181 input();182 solve();183 output();184 }185 return 0;186 }
HDU 1535 Invitation Cards (最短路，附SLF优化SPFA)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。