首页 > 代码库 > EOJ 1848 你是ACM吗？ 用二叉堆优化dijkstra + spfa算法的学习
EOJ 1848 你是ACM吗？ 用二叉堆优化dijkstra + spfa算法的学习
Description
随着中国经济的腾飞，中国的物流产业迎来了发展的春天。特别是在上海这样一个拥有广阔国内腹地的国际化大都市，物流业以空前的速度膨胀。
当然是大蛋糕就会吸引许多馋嘴猫，馋嘴猫多了就会有残酷的竞争。当大量资金流入物流产业时，KOP 集团为了稳坐在国内物流业的第一把交椅，决定对现行的运输方案进行改良，以减少自己的成本同时使其它竞争者知难而退。
作为世界100强的KOP集团当然知道要找到最优运输方案，肯定得靠数学和算法很好的软件工程师，于是他们理所当然地找到华东师范大学软件学院。决定通过赞助一场程序比赛来找出最优秀的工程师( ACM : Ace Coding Man )。
比赛只有一道题目，是运输线路的简单抽象，题意如下：
SH 市有N个运输中转点(简单标示为 1,2,3,....,N)，中转点之间可能有一条运输线路，这条线路有一个特殊的地方就是从A 到B点需要耗费 c1 个单位的查克拉(SH市的货币单位)，但从B到A可能需要 c2 个查克拉。当然c1不一定等于c2，也能从A到B之后就不能从B返回A了。你可以理解为这些线路是“单向”的。线路总共有 M 条。每天有N-1辆车从KOP集团总部(这里假设就是标号为1的中转点)，出发，分别发往N-1个剩下的中转点，然后当天再从所到达的中转点返回。你的任务就是要求出一天的最小耗费。
Input
第一行为 C ，表示有C个测试用列。接下来分别为C个测试用列。
每个测试用例的格式如下：
第一行为两个整数，N，M ,分别表示有N个中转点和M条道路。( 1=< N, M <=1000000 .);
紧接着的M 行每行有三个值 A B c； 分别表示从中转点A到中转点B需要耗费 c 个单位的查克拉。 ( 0<= c <= 1000000000 ).
Output
你的输出应该包括C行，每行输出一个值，对应于相应的用列的最少耗费。
Sample Input
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
Sample Output
46
210
题目分析：给出一个有向图图，保证是联通的，求1到所有点的最小距离和加上所有点到1的最小距离和的总和，只需要分别把边正向存储和反向存储一次，做两次单源最短路径算法即可。因为点数量很多，所以要用邻接表的方法来存储图，同时使用邻接图还可以减少枚举数量，提高效率。可用1.二叉堆优化dijkstra的方法和2.spfa算法完成。
方法一：二叉堆优化dijkstra.将每个点当前到源点的最短距离放入堆中，每次就可在logn时间复杂度取出，每次再把利用新加入的点更新的距离放入堆中，为区别一个点是否加入源点所在集合，加一个标记数组即可，整体思路和普通dijkstra相近。AC代码见下。
方法二：spfa算法。其复杂度为 O（KE），E为边数，K为平均每个点更新次数，通常小于2。算法主要思想：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前最短路径值对u点所指向的结点v进行松弛操作，如果v点的最短路径值有所调整，且 v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。因为每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。
对比：方法一是用堆优化dijkstra每次寻找最短估计距离的效率，标记数组标记一个点是否已经加入源点所在集合，即已经最优。方法二是不断更新每个点的最短距离估计值，直到不能更新位置，思想是不断逼近最优解。同样需要一个标记数组标记一个点是否已在队中（防止在队中的点再次入队已提高效率）。另外dijkstra不能处理带负权的图，spfa可以，但需要判断是否存在权为负的回路（即是否有点入队n次）。
Dijkstra AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN=1000001;
const long long INF=1000000001;
struct Edge{
int from,to,dist;
};
int n,m;
vector<Edge> edge[2];
vector<int> g[2][MAXN];
long long d[2][MAXN];
bool vis[MAXN];
struct Node{
long long d;
int u;
bool operator<(const Node& x)const{
return d>x.d;
}
};
void addedge(int from,int to,int dis,intk){
edge[k].push_back((Edge){from,to,dis});
int t=edge[k].size();
g[k][from].push_back(t-1);
}
void dijkstra(int s,int k){
priority_queue<Node> q;
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;++i) d[k][i]=INF;
d[k][s]=0;
q.push((Node){0,s});
while(!q.empty()){
Node x=q.top();q.pop();
int u=x.u;
if(vis[u]) continue;
vis[u]=true;
for(int i=0;i<g[k][u].size();++i){
Edge &e=edge[k][g[k][u][i]];
if(d[k][u]+e.dist<d[k][e.to]){
d[k][e.to]=d[k][u]+e.dist;
q.push((Node){d[k][e.to],e.to});
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
edge[1].clear();edge[0].clear();
for(int i=0;i<=n;++i){
g[0][i].clear();
g[1][i].clear();
}
for(int i=0;i<m;++i){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c,0);
addedge(b,a,c,1);
}
dijkstra(1,0);
dijkstra(1,1);
long long ans=0;
for(int i=2;i<=n;++i)
ans+=d[0][i]+d[1][i];
printf("%I64d\n",ans);
}
return 0;
}
Spfa AC代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <list>
#include <queue>
using namespace std;
struct E{
int e,cost,next;
}e[2][1000005];
bool vis[1000005];
long long low[1000005];
int head[2][1000005];
void spfa(int k){
memset(vis,false,sizeof(vis));
int i;
for(i=0;i<1000005;++i) low[i]=1e10;
vis[1]=true;
low[1]=0;
queue<int> q;
q.push(1);
while(!q.empty()){
int tem=q.front();
q.pop();
vis[tem]=false;
for(i=head[k][tem];i!=-1;i=e[k][i].next){
int en=e[k][i].e;
if(low[tem]+e[k][i].cost<low[en]){
low[en]=low[tem]+e[k][i].cost;
if(!vis[en]){
vis[en]=true;
q.push(en);
}
}
}
}
}
int main()
{
int t,i;
scanf("%d",&t);
while(t--){
int m,n,a,b,c;
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(i=0;i<m;++i){
scanf("%d%d%d",&a,&b,&c);
e[0][i].cost=e[1][i].cost=c;
e[0][i].e=b;
e[0][i].next=head[0][a];
head[0][a]=i;
e[1][i].e=a;
e[1][i].next=head[1][b];
head[1][b]=i;
}
long long ans=0;
spfa(0);
for(i=2;i<=n;++i){
ans+=low[i];
}
spfa(1);
for(i=2;i<=n;++i)
ans+=low[i];
printf("%lld\n",ans);
}
return 0;
}
EOJ 1848 你是ACM吗？ 用二叉堆优化dijkstra + spfa算法的学习