【算法】最短路径之Dijkstra（II）

1.问题

1.1 POJ 1062

建立有向图：比如，物品1能被替代品2所替代，且所需金币为200；则存在一条从点2到点1的边，且边长为200。

等级处理采用的是枚举。用rank[ ]表示每一节点的等级，节点0表示探险家，节点1表示国王。用M表示等级的限制，那么探险家可以交易的区间为[rank(1)-M, rank(1)] ，… ，[rank(1), rank(1)+M]。注：[ ]表示闭区间，rank(1)表示国王的等级。

关于所用枚举方法更具体的解释请参看这里。

最后一次WA，没有考虑极端情况：输入的N为100。将#define MAX 100改为#define MAX 101，就AC了。

源代码：

1062

Accepted

204K

32MS

C

1823B

2013-08-09 21:05:13

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#define MAX 101
#define inf 0xffffff

int edge[MAX][MAX];
int rank[MAX],trade[MAX];

void init(int N)
{
    int i,j,k,X;
	for(i=0;i<=N;i++)
	{
		for(j=0;j<i;j++)
		{
            edge[i][j]=edge[j][i]=inf;
		}
		edge[i][i]=0;
	}
	
	for(i=1;i<=N;i++)
	{
		scanf("%d%d%d",&edge[0][i],&rank[i],&X);
		for(j=0;j<X;j++)
		{
			scanf("%d",&k);
			scanf("%d",&edge[k][i]);
		}
	}
}

int smaller(int be,int af)
{
    return be<=af?be:af;
}

int dijkstra(int N)
{
    int i,count=1,temp,min_lowcost,min_node;
    int *lowcost=(int *) malloc((N+1)*sizeof(int));
    int *visit=(int *) malloc((N+1)*sizeof(int));
	
    for(i=0;i<=N;i++)
    {
        lowcost[i]=(i==0?0:inf);
        visit[i]=(i==0?1:0);
    }	
    min_node=0;
	
    while(count<=N)
    {
        min_lowcost=inf; 
		
        for(i=1;i<=N;i++)
        {
            if(trade[i]&&!visit[i]&&edge[min_node][i]!=inf)
                lowcost[i]=smaller(lowcost[i],lowcost[min_node]+edge[min_node][i]);
        }
		
        for(i=1;i<=N;i++)
            if(trade[i]&&!visit[i]&&lowcost[i]<min_lowcost)
            {
                min_lowcost=lowcost[i];
                min_node=i;
            }
			visit[min_node]=1;
			count++;
    }
    temp=lowcost[1];
    free(lowcost);
    free(visit);
	return temp;
}

int main()
{
    int i,j,rank_limit,N,min_god=inf;
    while(scanf("%d%d",&rank_limit,&N)!=EOF)
	{
		init(N);		
		for(i=0;i<=rank_limit;i++)
		{
			memset(trade,0,(N+1)*sizeof(int));
			trade[0]=trade[1]=1;
			for(j=2;j<=N;j++)
			{
				if(rank[j]>=rank[1]-rank_limit+i&&rank[j]<=rank[1]+i)
					trade[j]=1;
			}
			min_god=smaller(min_god,dijkstra(N));
		}
		printf("%d\n",min_god);
	}
    return 0;
	
}

1.2 POJ 1797

该问题可用(n,m)图来描述：crossings是图的顶点，streets是图的边；源点是标号为1的顶点，汇点是标号为n的顶点。源点到汇点的每一通路均有一条最短边，在这些最短边中找出最大值，此最大值即为the maximum allowed weight。

与之相类似的是POJ 2253，POJ 2253求解的是最小最长边，而POJ 1797求解最大最短边。

同样地，修改松弛条件：dis[i]=max{min{dis[j],edge[j][i]},dis[i]}

其中，dis[i]记录源点到点i所有通路的最短边。

用memset( )初始化动态数组时，在指定大小时不能直接sizeof(数组名)。如：memset(dis,0,sizeof(dis))就是错误的，并不能将动态数组全部置0。

源代码：

1797

Accepted

4080K

485MS

C

1338B

2013-08-11 18:30:42

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#define MAX 1000
#define inf 0xffffff

int edge[MAX][MAX];

void init(int n,int m)
{
	int i,start,end;
	memset(edge,0,sizeof(edge));
	for(i=0;i<m;i++)
	{
		scanf("%d%d",&start,&end);
		scanf("%d",&edge[start-1][end-1]);
		edge[end-1][start-1]=edge[start-1][end-1];
	}		
}

int smaller(int be,int af)
{
	return be<=af?be:af;
}

int larger(int be,int af)
{
	return be>=af?be:af;
}

void dijkstra(int n)
{
	int i,count=1,max_node,max_dis;
	int *dis=(int *) malloc(n*sizeof(int));
	int *visit=(int *) malloc(n*sizeof(int));
	
	memset(dis,0,n*sizeof(int));
	memset(visit,0,n*sizeof(int));
	dis[0]=inf;
	visit[0]=1;
	max_node=0;
	
	while(count<n)
	{
        max_dis=0; 
		
		for(i=1;i<n;i++)
		{
			if(!visit[i]&&edge[max_node][i]!=0)
				dis[i]=larger(smaller(dis[max_node],edge[max_node][i]),dis[i]);
		}

		for(i=1;i<n;i++)
		{
			if(!visit[i]&&dis[i]>max_dis)
			{
				max_dis=dis[i];
				max_node=i;
			}
		}
		visit[max_node]=1;     	
		count++;			
	}
	printf("%d\n\n",dis[n-1]);
	free(dis);
	free(visit);
}

int main()
{
	int test_case,i,n,m;
	scanf("%d",&test_case);
	for(i=0;i<test_case;i++)
	{
		scanf("%d%d",&n,&m);
		init(n,m);
		printf("Scenario #%d:\n",i+1);
		dijkstra(n);
	}
	return 0;
}

1.3 POJ 3268

题目大意：每一个农场都有一只cow，cow们要去农场X参加party，当party结束后返回自己的农场。cow非常懒，去程与返程都选择最短路径。求：在所有的cow中，去程+返程花费最多的时间是多少？

思路：将农场X看作源点，其他的农场均看作汇点，去程的最短路径用Dijkstra即可求的。然后将图的邻接矩阵转置，再次用Dijkstra，并还将农场X看作源点，其余点是汇点（参考Discuss）。

源代码：

3268

Accepted

4076K

94MS

C

1779B

2013-08-11 22:09:40

#include "stdio.h"
#include "stdlib.h"

#define MAX 1000
#define inf 0xffffff

int edge[MAX][MAX];

void init(int N,int M)
{
    int i,j,start,end;

/*initialize the edge*/
	for(i=0;i<N;i++)  
    {  
        for(j=0;j<i;j++)   
            edge[i][j]=edge[j][i]=inf;   
        edge[i][i]=0;  
    }
	
    for(i=0;i<M;i++)
	{
		scanf("%d%d",&start,&end);
		scanf("%d",&edge[start-1][end-1]);
	}
}

int larger(int be,int af)
{
	return be>=af?be:af;
}

int smaller(int be,int af)
{
    return be<=af?be:af;
}

void dijkstra(int N,int X,int lowcost[])
{
    int i,count=1,min_lowcost,min_node;
    int *visit=(int *) malloc(N*sizeof(int));
	
    for(i=0;i<N;i++)
    {
        lowcost[i]=inf;
        visit[i]=0;
    }
	
/*set the source node as X*/
    lowcost[X-1]=0;
    visit[X-1]=1;
    min_node=X-1;
	
    while(count<N)
    {
        min_lowcost=inf; 
		
        for(i=0;i<N;i++)
        {
            if(!visit[i]&&edge[min_node][i]!=inf)
                lowcost[i]=smaller(lowcost[i],lowcost[min_node]+edge[min_node][i]);
        }
		
        for(i=0;i<N;i++)
            if(!visit[i]&&lowcost[i]<min_lowcost)
            {
                min_lowcost=lowcost[i];
                min_node=i;
            }
			
			visit[min_node]=1;
			count++;
    }
	
    free(visit);
}

void transpose(int N)
{
    int i,j,temp;
	for(i=0;i<N;i++)
		for(j=0;j<i;j++)
		{
			temp=edge[i][j];
			edge[i][j]=edge[j][i];
			edge[j][i]=temp;
		}
}

int main()
{
    int i,N,M,X,longest=0;
	int to[MAX],back[MAX];
    scanf("%d%d%d",&N,&M,&X);                
    init(N,M); 
	
    dijkstra(N,X,to);
    transpose(N);
	dijkstra(N,X,back);
	
/*find the longest trip*/
	for(i=0;i<N;i++)
        longest=larger(longest,to[i]+back[i]);
	printf("%d\n",longest);	
    return 0;
}