`
249326109
  • 浏览: 56053 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

pat 1003. Emergency (25)

 
阅读更多

链接:http://pat.zju.edu.cn/contests/pat-a-practise/1003

 

题意:计算两个点之间的加权最短路径,若有多条最短路径,选取沿途节点权重和最大的。

 

分析:利用Dijkstra算法求出最短路径,然后利用dfs遍历选取路径最短并且节点权重最大。

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define Inf 100000000

int road[505][505];
int people[505];
int n, m, from, to;

int known[505];
int d[505];
int p[505];

int visited[505];
int maxNum = -1;
int pathNum = 0;

//void printStatus() {
//	int i;
//	printf("known:");
//	for (i = 0; i < n; i++) {
//		printf("%d ", known[i]);
//	}
//	printf("d:");
//	for (i = 0; i < n; i++) {
//		printf("%d ", d[i]);
//	}
//
//	printf("p:");
//	for (i = 0; i < n; i++) {
//		printf("%d ", p[i]);
//	}
//	printf("\n");
//}

int getMin() {
	int i;
	int min = Inf;
	int minIdx = -1;
	for (i = 0; i < n; i++) {
		if (!known[i] && d[i] < min) {
			min = d[i];
			minIdx = i;
		}
	}
	return minIdx;

}

void dijkstra() {
	//init
	memset(known, 0, sizeof(known));
	memset(p, -1, sizeof(p));
	int i;
	for (i = 0; i < n; i++)
		d[i] = Inf;

	d[from] = 0;
//	printStatus();
	//loop
	int min;
	while (1) {
		min = getMin();
		if (min == -1)
			break;

		known[min] = 1;
		int j;
		for (j = 0; j < n; j++) {
			if (road[min][j]) {
				if (!known[j])
					if (d[min] + road[min][j] < d[j]) {
						d[j] = d[min] + road[min][j];
						p[j] = min;
					}

			}

		}

	}

}

//void printPath(int to) {
//	if (p[to] != -1)
//		printPath(p[to]);
//	printf("%d ", to);
//}

void dfs(int city, int dis, int peoNum) {
	if (city == to && dis == d[to]) {
		pathNum++;
		if (peoNum > maxNum)
			maxNum = peoNum;
	}
	if(dis>d[to])
		return;
	int i;
	for (i = 0; i < n; i++) {
		if (road[city][i] && !visited[i]) {
			visited[i] = 1;
			dfs(i, dis + road[city][i], peoNum + people[i]);
			visited[i] = 0;
		}
	}

}

int main() {
	scanf("%d%d%d%d", &n, &m, &from, &to);
	int i;
	for (i = 0; i < n; i++)
		scanf("%d", &people[i]);
	int a, b, dis;
	for (i = 0; i < m; i++) {
		scanf("%d%d%d", &a, &b, &dis);
		road[a][b] = dis;
		road[b][a] = dis;
	}
	dijkstra();
//	printStatus();

//	printPath(to);

	dfs(from, 0, people[from]);
	printf("%d %d\n", pathNum, maxNum);

	return 0;
}

 

分享到:
评论

相关推荐

    浙江大学pat题目集合(1001-1080)

    1003. Emergency (25) 是一个涉及到图论和最短路径问题的题目。题目描述了一个城市救援团队接到紧急任务后,如何快速规划路线并调动沿途城市的救援力量。输入包含一个案例,案例信息包括各个城市的救援队伍数量和...

    浙江大学pat题目集合(1001-1072)

    1003. Emergency(25分): 这道题与图论和最短路径计算相关。模拟了一个城市紧急救援队队长的角色,需要根据地图上的城市和道路信息,找出从出发城市到目标城市的最短路线,并沿途动员最多的救援队伍。输入包含一个...

    pat题目分类.docx

    - **最短路径算法** (如1003 Emergency, 1072 Gas Station, 1087 All Roads Lead to Rome, 1030 Travel Plan): 主要涉及Dijkstra算法,需要理解和实现这个经典算法。 - **最大团问题** (1142 Maximal Clique): ...

    PAT甲级题解.pdf

    3. Dijkstra算法:尽管在文件片段中没有详细解释Dijkstra算法,但根据题名"Emergency"(编号1003)可以推测,这个问题可能涉及图论中的单源最短路径问题。Dijkstra算法是一种用于在加权图中找到从单一源点到所有其他...

    PAT 题目精解但(包括1000题)

    例如,1003题"Emergency"可能涉及到使用贪心策略来解决问题。解题时,需要从问题描述出发,确定贪心选择的标准,然后构建局部最优解,直至得到全局最优解。 4. Dijkstra算法:在图论和网络流问题中,Dijkstra算法是...

    浙江大学pat题目集合(1001-1091)

    1003题——Emergency,此题模拟了一个紧急救援团队队长的场景。你需要根据给定的城市地图,找出从当前城市出发到达目标城市最快的路线,并在途中动员尽可能多的救援队伍。输入案例包含了城市之间的连接信息,包括每...

    PAT甲级真题练习1

    3. Emergency (25) Emergency是一个中等难度的字符串处理题,要求考生编写一个程序来处理紧急情况的信息。该题目考察了考生的字符串处理能力和算法设计能力。 知识点: * 字符串处理 * 条件语句 * 循环语句 4. ...

    pat题集word

    **题1003:Emergency (25)** 这个题目可能是关于路径规划和最优化的问题,模拟紧急救援情况。你可能需要读取一个城市地图的数据,包括各城市之间的连接道路以及救援队伍数量和道路长度。你的任务是在接到紧急呼叫时...

    程序员刷题judge-PAT_Solutions::lollipop:MyPAT(AdvancedLevel)练习解决方案

    Emergency(25 分) 解题思路 先通过 dijkstra 算法求出最短的路径长度,之后从终点回溯 dfs,记录满足:dis[u] + cost(u, v) = dis[v] 的点,生成路径。递归出口:u 是起点。 先用 dijkstra 算法求出最短路,使用 ...

    北师大版高中英语选修7(部分单词表)

    - **例句**:“In case of emergency, please use the nearest exit.”(紧急情况下,请使用最近的出口。) #### dilemma - **含义**:困境;进退两难的窘境 - **例句**:“He faced a dilemma between choosing ...

Global site tag (gtag.js) - Google Analytics