1. 原题：https://www.patest.cn/contests/pat-a-practise/1003
2. 思路：
题意：给出一个无向带权图，求某两点间的最短路径条数。
思路：
单源最短路径问题。
可用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;
}
