CityMap-c语言

CityMAP

问题描述

分析

代码实现（dfs）

#include <stdio.h>
int e[51][51] ;//邻接矩阵表示法存储地图的二维数组
int book[51] ;//标记遍历的点
int n, m,dis,min=9999999;
void dfs(int cur, int dis) {
	if (cur == n) {//如果当前点是终点
		if (dis < min) {
			min = dis;
		
	}
	}
	
	if (dis > min)
		return;
	int j;
	for (j = 1; j <= n; j++) {//从1~n依次遍历
		if (e[cur][j] != 0 && book[j] == 0) {
			//判断当前点到j点是否有路且未标记
			book[j] = 1;
			dfs(j, dis + e[cur][j]);

		}
	}
	book[cur] = 0;
	return;
}
int main() {
	int i, j, a,b,c;
	
	scanf_s("%d %d", &n, &m);
	for (i = 1; i <= m; i++) {
		scanf_s("%d %d %d", &a, &b, &c);
		e[a][b] = c;
	}
	book[1] = 1;
	dfs(1, 0);
	printf("%d", min);
	getchar(); getchar();
	return 0;
}

输入

5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3

输出

9

总结

最少转机

问题描述

分析

代码实现（bfs）

#include <stdio.h>
struct note {
	int x;
	int s;
};
int main(){
	int i, j, n, m, a,b,start, end,tail,head,flag=0;
	int e[51][51] = { 0 };
	int book[51] = { 0 };
	struct note que[2501];
	scanf_s("%d %d %d %d", &n, &m, &start, &end);
	for (i = 1; i <= m; i++) {
		scanf_s("%d %d", &a, &b);
		e[a][b] = 1;
		e[b][a] = 1;
	}
	tail = 1;
	head = 1;
	que[tail].x = start;
	que[tail].s = 0;
	book[start] = 1;
	tail++;//不要忘记！！
	while (head < tail) {
		int cur;
		cur = que[head].x;
		
		
		for (i = 1; i <= n; i++) {
			if (e[cur][i] == 1 && book[i] == 0) {
				book[i] = 1;
				que[tail].x = i;
				que[tail].s = que[head].s + 1;
				tail++;
			}
			if (que[tail].x == end) {
				flag = 1;
				break;
			}
				
			
		}
		if (flag == 1)
			break;
		head++;
	}
	printf("%d", que[tail-1].s);
	getchar(); getchar();
	return 0;
}

输入

5 7 1 5
1 2
1 3
2 3
2 4
3 4
3 5
4 5

输出

2