【最短路/3大模板】总结【2012-1-22新增前插的spfa】
http://dl.iteye.com/upload/attachment/544682/0ca3f693-db83-35da-b50e-b0c8f7acc4d8.png首先献上模板：【点都是默认为从1到n编号，用dijk和floyd时要注意重边】
①DIJK#define inf 0x3fffffff#define M 105int dist, map, n;bool mark;void init (){int i, j;for (i = 1; i <= n; i++) //i==j的时候也可以初始化为0，只是有时候不合适for (j = 1; j <= n; j++)map = inf;}void dijk (int u){int i, j, mins, v;for (i = 1; i <= n; i++){dist = map;mark = false;}mark = true;dist = 0; //既然上面的map当i==j时不是0，就要这句while (1){mins = inf;for (j = 1; j <= n; j++)if (!mark && dist < mins)mins = dist, v = j;if (mins == inf)break;mark = true;for (j = 1; j <= n; j++)if (!mark && dist + map < dist)dist = dist + map;}}
②Floyd
#define inf 0x3fffffff//注意，太大会溢出#define M//最大点数int n, dist; //n：实际点数void init ()//有时候需要初始化{ int i, j; for (i = 1; i <= n; i++) for (j = i + 1; j <= n; j++) dist = dist = inf;}void floyd (){ int i, j, k; for (k = 1; k <= n; k++) for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) //有的题目会溢出就要自己变通了 if (dist + dist < dist) dist = dist + dist;}
③vector后插的SPFA
#define inf 0x3fffffff#define M 105 //最大点数struct son{ int v, w;};vector<son> g;bool inq; //入队列标记int dist, n; //n：实际点数void init (){for (int i = 1; i <= n; i++)g.clear();}void spfa (int u){ int i, v, w; for (i = 1; i <= n; i++) { dist = inf; inq = false; } queue<int> q; q.push (u); inq = true; dist = 0; while (!q.empty()) { u = q.front(); q.pop(); inq = false; for (i = 0; i < g.size(); i++) { v = g.v; w = g.w; if (dist + w < dist) { dist = dist + w; if (!inq) { q.push (v); inq = true; } } } }}
④模拟前插的SPFA(多数情况下比③快，数据较为复杂就会看出来)
#define inf 0x3fffffff#define M 1005//最大点数struct edge{ int v, w, next;}e;//估计好有多少条边int pre, cnt, dist, n;bool inq;//注意初始化void init (){ cnt = 0; memset (pre, -1, sizeof(pre));}//注意双向加边 void addedge (int u, int v, int w) //加边函数，慢慢模拟就会明白的{ e.v = v; e.w = w; e.next = pre;//接替已有边 pre = cnt++;//自己前插成为u派生的第一条边}void spfa (int u){ int v, w, i; for (i = 1; i <= n; i++)//对于从1到n的编号 dist = inf, inq = false; dist = 0; queue<int> q; q.push (u); inq = true; while (!q.empty()) { u = q.front(); q.pop(); inq = false; for (i = pre; i != -1; i = e.next) { w = e.w; v = e.v; if (dist + w < dist) { dist = dist + w; if (!inq) { q.push (v); inq = true; } } } }}
第一题：http://acm.hdu.edu.cn/showproblem.php?pid=2544
灰常水，floyd、dijk、spfa都可以
第二题：http://acm.hdu.edu.cn/showproblem.php?pid=2066
简单题，多源多终点，spfa、dijk都很快解决
第三题：http://acm.hdu.edu.cn/showproblem.php?pid=2112
用STL的map把地名映射到编号就可以套模板了，注意路是双向的就行了
第四题：http://acm.hdu.edu.cn/showproblem.php?pid=1874
和第一题一样的水
第五题：http://acm.hdu.edu.cn/showproblem.php?pid=1142
最短路+记忆化搜索
详情：http://972169909-qq-com.iteye.com/blog/1149589
第六题：http://acm.hdu.edu.cn/showproblem.php?pid=1385
floyd记忆路径
详情：http://972169909-qq-com.iteye.com/blog/1150803
第七题：http://acm.hdu.edu.cn/showproblem.php?pid=1548
水题，构图后直接dijk或spfa就可以了
第八题：http://acm.hdu.edu.cn/showproblem.php?pid=1217
floyd的灵活运用
详情：http://972169909-qq-com.iteye.com/blog/1149095
第九题：http://acm.hdu.edu.cn/showproblem.php?pid=2680
简单题，多起点单终点，反过来dijk或者spfa就可以了，注意路是单向的，所有路都要反过来，逆向思维
第十题：http://acm.hdu.edu.cn/showproblem.php?pid=2923
题目意思可能比较难懂，而且有重边，floyd
详情：http://972169909-qq-com.iteye.com/blog/1150818
第十一题：http://acm.hdu.edu.cn/showproblem.php?pid=2962
直接枚举或二分枚举+最短路
详情：http://972169909-qq-com.iteye.com/blog/1159652
第十二题：http://acm.hdu.edu.cn/showproblem.php?pid=2722
这题主要是构图麻烦，会用sscanf就比较好做了，构好图之后就是水题了
第十三题：http://acm.hdu.edu.cn/showproblem.php?pid=1690
暴力构图，枚举2点间距离，根据表格定好花费，然后直接floyd就可以了【注意数太大要用64位，无穷大定为-1比较好处理】
第十四题表示压力好大……
第十五题：http://acm.hdu.edu.cn/showproblem.php?pid=1596
floyd水题
第十六题：http://acm.hdu.edu.cn/showproblem.php?pid=1598
并查集+贪心 或 二分枚举+最短路
详情：http://972169909-qq-com.iteye.com/blog/1159593
第十七题表示不想做……
第十八题：http://acm.hdu.edu.cn/showproblem.php?pid=2363
枚举高度差+最短路，比较容易错
详情：http://972169909-qq-com.iteye.com/blog/1159650
第十九题表示很蛋疼……
第二十题：http://acm.hdu.edu.cn/showproblem.php?pid=2833
一题比较难的记忆化搜索+最短路【或dp+最短路】
详情：http://972169909-qq-com.iteye.com/blog/1159661
页:
[1]