本文主要是介绍1003. Emergency (25)[dfs]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 原题：https://www.patest.cn/contests/pat-a-practise/1003
2. 思路：
题意：给出一个无向带权图，求某两点间的最短路径条数。
思路：
单源最短路径问题。
可用DFS, 或者diskstra, dfs简单些;
思路：
单源最短路径问题。
可用DFS, 或者diskstra, dfs简单些;
已AC
3. 源码：
#include <iostream>
using namespace std;const int INF = 0x7ffffff;
const int MAX = 501;
int mp[MAX][MAX];
int N, M, c1, c2;//分别为城市数，路径数，起点，终点
int visited[MAX] = { 0 };//1表示某点已访问
int team[MAX] = { 0 };//某点的队数
int pathNum = 0;//所求路径数
int maxTeam = 0;//最大队数
int sp = INF;//最短路径长度void dfs(int st, int wpl, int myteam);//参数为起点，当前路径长度，当前队数int main(void)
{//freopen("in.txt", "r", stdin);scanf("%d %d %d %d", &N, &M, &c1, &c2);for (int i = 0; i < N; i++)//图的初始化{for (int j = 0; j < N; j++){mp[i][j] = INF;}}for (int i = 0; i < N; i++){scanf("%d", &team[i]);}for (int i = 0; i < M; i++){int s, d, wt;scanf("%d %d %d", &s, &d, &wt);mp[s][d] = mp[d][s] = wt;}dfs(c1, 0, team[c1]);//dfs递归printf("%d %d\n", pathNum, maxTeam);return 0;
}void dfs(int st, int wpl, int myteam)
{visited[st] = 1;if (wpl > sp)//剪枝优化，return;if (st == c2)//分情况处理最短路{if (wpl < sp){pathNum = 1;maxTeam = myteam;sp = wpl;}else if (wpl == sp){pathNum++;maxTeam = (maxTeam < myteam ? myteam : maxTeam);}return;}for (int i = 0; i < N; i++){if (visited[i] == 0 && mp[st][i] < INF){dfs(i, wpl + mp[st][i], myteam + team[i]);visited[i] = 0;//访问完子结点，这里要设为未访问，以便后面的继续访问}}return;
}这篇关于1003. Emergency (25)[dfs]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
