lindi 530 의 'C 추억' (1) - 가장 짧 은 길 은 간단 하면 서도 틀 리 기 쉽다.

\ # # lindi 530 의 "C 추억" (1) - 가장 짧 은 길 은 간단 하면 서도 틀 리 기 쉽다.
예제: 모 성 은 여러 해 동안 의 원활 한 공사 계획 을 실시 한 후에 마침내 많은 길 을 건설 했다.길 을 많이 건 너 지 않 아 도 좋 지 않다. 한 도시 에서 다른 도시 로 갈 때마다 여러 가지 도로 방안 을 선택 할 수 있 고 어떤 방안 은 다른 방안 보다 걷 는 거리 가 훨씬 짧다.이것 은 행인 들 을 매우 곤란 하 게 한다.지금 은 출발점 과 종점 을 알 고 있 습 니 다. 출발점 에서 종점 까지 가장 짧 은 거 리 를 걸 어야 하 는 지 계산 해 보 세 요.
Input 이 문 제 는 여러 그룹의 데 이 터 를 포함 하고 있 습 니 다. 파일 이 끝 날 때 까지 처리 하 십시오.각 조 의 데이터 첫 줄 에는 두 개의 정수 N 과 M (0 다음은 M 행 도로 정보 가 포함 되 어 있 습 니 다. 각 줄 에는 세 개의 정수 A, B, X (0 < = A, B 가 다음 줄 에 두 개의 정수 S, T (0 < = S, T) 가 있 습 니 다.
출력 은 각 그룹의 데이터 에 대해 한 줄 에 걸 어야 할 가장 짧 은 거 리 를 출력 하 십시오. S 에서 T 까지 의 경로 가 존재 하지 않 는 다 면 출력 - 1 Sample Input 3 3 0 1 1 0 2 3 1 2 1 2 1 0 2 3 1 1 1 1 1 1 2 Sample Output 2 - 1
/*    ,      */
#include
#include
#define inf 999999999
int p[500][500],book[500],dis[500];
int main()
{
     
	int n,m,i,j,k;
	while(~scanf("%d%d",&n,&m))
	{
     
		memset(p,0,sizeof(p));
		memset(dis,0,sizeof(dis));
		memset(book,0,sizeof(book));
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				if(i==j)
					p[i][j]=0;
				else
					p[i][j]=inf;
		int a,b,c;
		for(i=0;i<m;i++)
		{
     
			scanf("%d%d%d",&a,&b,&c);
			p[a][b]=c;
			p[b][a]=c;
		}
		int x,y,min,u;
		scanf("%d%d",&x,&y);
		for(i=0;i<n;i++)
			dis[i]=p[x][i];
		book[x]=1;
		for(i=0;i<n;i++)
		{
     
			min=inf;
			for(j=0;j<n;j++)
			{
     
				if(book[j]==0&&dis[j]<min)
				{
     
					min=dis[j];
					u=j;
				}
			}
			book[u]=1;
			for(j=0;j<n;j++)
				if(dis[j]>min+p[u][j])
					dis[j]=min+p[u][j];
		}
		if(dis[y]!=inf)
			printf("%d
"
,dis[y]); else printf("-1
"
); } return 0; }

이 코드 를 보고 많은 초보 동료 들 이 옳다 고 생각 할 것 이다. 사실은 그렇지 않다.
		for(i=0;i<m;i++)
		{
     
			scanf("%d%d%d",&a,&b,&c);
			p[a][b]=c;
			p[b][a]=c;
		}

예 를 들 어 두 그룹의 데이터 1, 2, 3, 1, 2, 6 이 배열 에 저 장 된 p [1] [2] = 3 은 덮어 쓰 이 고 입력 이 끝 났 을 때 p [1] [2] = 6 은 문제 의 뜻 에 부합 되 지 않 는 최 단 거리 가 뚜렷 하 며 판단 조건 을 추가 하면 된다.
		for(j=0;j<n;j++)
		{
     
			if(book[j]==0&&dis[j]<min)
			{
     
				min=dis[j];
				u=j;
			}
		}

시합 할 때 생각 지도 못 했 는데, 한참 동안 끊 겼 는데, 아이고...

좋은 웹페이지 즐겨찾기