Favorite City (DFS)

Title description:

One day, Xiao Ming was reading a world map. Suddenly he picked up a pen and marked his favorite cities, and randomly connected some of them with line segments. Ming measured the length of each line segment, and now Ming wants to know what is the shortest distance between any two cities in the graph of these line segments.

Input:

The input contains multiple sets of test data. Each group input the first line of two positive integers n (n <=10) and m (m<=n*(n-1)/2), where n represents the number of cities and M represents the number of line segments. Next, enter three integers A, B, and L in each line, indicating that there is a line segment between city A and city B, and the length of the line segment is L. (a differs from B) Enter two integers x and y on the last line of each group to indicate the question: what is the shortest distance between x city and Y city. (x differs from y) The city is numbered from 1 to n, and L <=20.

Output:

For each group of inputs, output the shortest distance between city X and city Y. If city X and city Y are disconnected, output “No path”.

Example Input:

4 4

1 2 4

1 3 1

1 4 1

2 3 1

2 4

Sample output:

3

Program code:

#include<stdio.h>
#include<string.h>
void dfs(int startx,int sum);
int book[110],s[110] [110],j,m,n,x,y,min;
int main(a)
{
	int i,a,b,c;
	while(scanf("%d%d",&n,&m)! =EOF) { min=99999999;
		memset(book,0.sizeof(book));
		for(i=1; i<=n; i++)for(j=1; j<=n; j++) {if(i==j)
					s[i][j]=0;
				else
					s[i][j]=99999999;
			}
		for(i=1; i<=m; i++) {scanf("%d%d%d",&a,&b,&c);
			s[a][b]=c;
			s[b][a]=c;
		}
		scanf("%d%d",&x,&y);
		book[x]=1;
		dfs(x,0);
		if(min==99999999)
			printf("No path\n");
		else
			printf("%d\n",min);
	}
	return 0;
}
void dfs(int startx,int sum)
{
	int i;
	if(sum>=min)
		return;
	if(startx==y)
	{
		if(sum<min)
			min=sum;
		return;
	}
	for(i=1; i<=n; i++) {if(book[i]==0&&s[startx][i]! =99999999)
		{
			book[i]=1;
			dfs(i,sum+s[startx][i]);
			book[i]=0; }}return;
}
Copy the code