链接: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; }
相关推荐
1003. Emergency (25) 是一个涉及到图论和最短路径问题的题目。题目描述了一个城市救援团队接到紧急任务后,如何快速规划路线并调动沿途城市的救援力量。输入包含一个案例,案例信息包括各个城市的救援队伍数量和...
1003. Emergency(25分): 这道题与图论和最短路径计算相关。模拟了一个城市紧急救援队队长的角色,需要根据地图上的城市和道路信息,找出从出发城市到目标城市的最短路线,并沿途动员最多的救援队伍。输入包含一个...
- **最短路径算法** (如1003 Emergency, 1072 Gas Station, 1087 All Roads Lead to Rome, 1030 Travel Plan): 主要涉及Dijkstra算法,需要理解和实现这个经典算法。 - **最大团问题** (1142 Maximal Clique): ...
3. Dijkstra算法:尽管在文件片段中没有详细解释Dijkstra算法,但根据题名"Emergency"(编号1003)可以推测,这个问题可能涉及图论中的单源最短路径问题。Dijkstra算法是一种用于在加权图中找到从单一源点到所有其他...
例如,1003题"Emergency"可能涉及到使用贪心策略来解决问题。解题时,需要从问题描述出发,确定贪心选择的标准,然后构建局部最优解,直至得到全局最优解。 4. Dijkstra算法:在图论和网络流问题中,Dijkstra算法是...
1003题——Emergency,此题模拟了一个紧急救援团队队长的场景。你需要根据给定的城市地图,找出从当前城市出发到达目标城市最快的路线,并在途中动员尽可能多的救援队伍。输入案例包含了城市之间的连接信息,包括每...
3. Emergency (25) Emergency是一个中等难度的字符串处理题,要求考生编写一个程序来处理紧急情况的信息。该题目考察了考生的字符串处理能力和算法设计能力。 知识点: * 字符串处理 * 条件语句 * 循环语句 4. ...
**题1003:Emergency (25)** 这个题目可能是关于路径规划和最优化的问题,模拟紧急救援情况。你可能需要读取一个城市地图的数据,包括各城市之间的连接道路以及救援队伍数量和道路长度。你的任务是在接到紧急呼叫时...
Emergency(25 分) 解题思路 先通过 dijkstra 算法求出最短的路径长度,之后从终点回溯 dfs,记录满足:dis[u] + cost(u, v) = dis[v] 的点,生成路径。递归出口:u 是起点。 先用 dijkstra 算法求出最短路,使用 ...
- **例句**:“In case of emergency, please use the nearest exit.”(紧急情况下,请使用最近的出口。) #### dilemma - **含义**:困境;进退两难的窘境 - **例句**:“He faced a dilemma between choosing ...