Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

贴个AC代码

Posted by 15211160230 at 2016-08-08 18:22:56 on Problem 2457
最短路路径生成的基础题,直接写出来了一气呵成
#include <stdio.h>
#include <limits.h>
#define MAXN 1001
int G[MAXN][MAXN],vexnum;
void Initial(int N)
{	int i,j;
	for(i=0;i<=N;++i)
		for(j=0;j<=N;++j)
			G[i][j]=INT_MAX;
	vexnum=N;
}
int FindMin(int dis[],int visited[])
{	int k=-1,min=INT_MAX,i;
	for(i=1;i<=vexnum;++i)
	{	if(visited[i]==1)	continue;
		if(dis[i]<min)
		{	k=i;
			min=dis[i];
		}	
	}
	return k;
}
void Dijkatra(int k,int D)
{	int dis[MAXN],visited[MAXN],i,pre[MAXN];
	for(i=1;i<=vexnum;++i)
	{	dis[i]=G[k][i],visited[i]=0;
		if(dis[i]!=INT_MAX)		pre[i]=k;
	}
	dis[k]=0,visited[k]=1,pre[k]=k;
	while(1)
	{	k=FindMin(dis,visited);
		if(k==-1)	break;
		visited[k]=1;
		for(i=1;i<=vexnum;++i)
		{	if(visited[i]==1||G[k][i]==INT_MAX)		continue;
			if(dis[i]>dis[k]+G[k][i])
			{	dis[i]=dis[k]+G[k][i];
				pre[i]=k;
			}
		}
	}
	if(dis[D]==INT_MAX)		puts("-1");
	else
	{	int res[MAXN],len=0;
		k=D;
		res[len++]=D;
		while(k!=pre[k])
		{	res[len++]=pre[k];
			k=pre[k];
		}
		printf("%d\n",len);
		for(i=len-1;i>=0;--i)
			printf("%d\n",res[i]);
	} 
}
int main()
{	int N,K;
	int a,b;
	while(scanf("%d %d",&N,&K)!=EOF)
	{	Initial(K);
		while(N--)
		{	scanf("%d %d",&a,&b);
			G[a][b]=1;
		}
		Dijkatra(1,K);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator