鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 手机系统开发 > J2ME > >

hdu2544最短路-裸的flody-dijkstra-spfa

来源:互联网 作者:佚名 时间:2015-09-25 05:39
//由于想 学习 spfa,所以把老题翻出来做做,也是很不错的,最近对dijkstra算法的掌握自己感觉还可以,就是千万要注意的是:在给dis[j]赋的时候,经常我都是搞错了大于小于号,不应该啊---------总结一下就是:要是求的是 关于 最短的,最小之类的,就是判断

//由于想学习spfa,所以把老题翻出来做做,也是很不错的,最近对dijkstra算法的掌握自己感觉还可以,就是千万要注意的是:在给dis[j]赋值的时候,经常我都是搞错了大于小于号,不应该啊---------总结一下就是:要是求的是关于最短的,最小之类的,就是判断dis[j]>map[][]+dis[k],其中给MIN赋值的时候,就是INF

反过来,要是求最大的,则就是判断:dis[j]<map[][]+dis[k],给MIN赋值的时候就是-INF(表示无穷小的意思)

flody代码:

#include<cstdio>
#include<iostream>
#include<queue>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long LL;
#define clr(x) memset(x,0,sizeof(x));
#define sf scanf
#define pf printf
int n,m;
int map[1002][1002];
#define INF 1<<29
void flody(){
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
            }
}
void init(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(i==j) map[i][j]=0;
            else map[i][j]=INF;
        }
}
int main(){
    int a,b,c;
    while(sf("%d%d",&n,&m)!=EOF&&(n+m)){
        init();
        for(int i=1;i<=m;i++){
            sf("%d%d%d",&a,&b,&c);
            map[a][b]=map[b][a]=c;
        }
        flody();
        pf("%d\n",map[1][n]);
    }
    return 0;
}


 

 

dijkstra代码1:

#include<cstdio>
#include<iostream>
#include<queue>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long LL;
#define clr(x) memset(x,0,sizeof(x));
#define sf scanf
#define pf printf
int n,m;
int map[1002][1002];
int dis[1001];
int vis[1001];
#define INF 1<<29
void dijkstra(int s){
    int k=0;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        dis[i]=map[s][i];
    }
    vis[s]=1;
    dis[s]=0;
    for(int i=1;i<=n;i++){
        int MIN=INF;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&dis[j]<MIN){
                MIN=dis[j];
                k=j;
            }
        }
        vis[k]=1;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&dis[j]>dis[k]+map[k][j])
                dis[j]=map[k][j]+dis[k];
        }
    }
}
void init(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(i==j) map[i][j]=0;
            else map[i][j]=INF;
        }
}
int main(){
    int a,b,c;
    while(sf("%d%d",&n,&m)!=EOF&&(n+m)){
        init();
        for(int i=1;i<=m;i++){
            sf("%d%d%d",&a,&b,&c);
            map[a][b]=map[b][a]=c;
        }
        dijkstra(1);
        pf("%d\n",dis[n]);
    }
    return 0;
}


 

 

dijkstra 代码2:

#include<cstdio>
#include<iostream>
#include<queue>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long LL;
#define clr(x) memset(x,0,sizeof(x));
#define sf scanf
#define pf printf
int n,m;
int map[1002][1002];
int dis[1001];
int vis[1001];
#define INF 1<<29
int dijkstra(int s,int t){
	int k=0;
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		dis[i]=map[s][i];
	}
	vis[s]=1;
	dis[s]=0;
	for(int i=1;i<=n;i++){
		int MIN=INF;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&dis[j]<MIN){
				MIN=dis[j];
				k=j;
			}
		}
		vis[k]=1;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&dis[j]>dis[k]+map[k][j])
				dis[j]=map[k][j]+dis[k];
		}
	}
	return dis[t];
}
void init(){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(i==j) map[i][j]=0;
			else map[i][j]=INF;
		}
}
int main(){
	int a,b,c;
	while(sf("%d%d",&n,&m)!=EOF&&(n+m)){
		init();
		for(int i=1;i<=m;i++){
			sf("%d%d%d",&a,&b,&c);
			map[a][b]=map[b][a]=c;
		}
		pf("%d\n",dijkstra(1,n));
	}
	return 0;
}


spfa 代码:

#include<cstdio>
#include<iostream>
#include<queue>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long LL;
#define clr(x) memset(x,0,sizeof(x));
#define sf scanf
#define pf printf
#define INF 1<<29
const int maxn=105;
int n,m;
int map[maxn][maxn];
int dis[maxn];
bool vis[maxn];
int spfa(int s,int t){
	queue<int>Q;
	while(!Q.empty()) Q.pop();
	memset(vis,false,sizeof(vis));
	for(int i=1;i<=n;i++)
		dis[i]=INF;
	dis[s]=0;
	vis[s]=true;
	Q.push(s);
	while(!Q.empty()){
		int now=Q.front();
		Q.pop();
		vis[now]=false;
		for(int i=1;i<=n;i++)
			if(dis[now]+map[i][now]<dis[i]){
				dis[i]=dis[now]+map[i][now];
				if(!vis[i]){
					vis[i]=true;
					Q.push(i);
				}
			}
	}
	return dis[t];
}
void init(){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(i==j) map[i][j]=0;
			else map[i][j]=INF;
		}
}
int main(){
	int a,b,c;
	while(sf("%d%d",&n,&m)&&n+m){
		init();
		for(int i=1;i<=m;i++){
			sf("%d%d%d",&a,&b,&c);
			map[a][b]=map[b][a]=c;
		}
		pf("%d\n",spfa(1,n));
	}
	return 0;
}
/*
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
*/


 

网友评论
<