1.首先我们要明确下目标：我们是需要对每一个起点找到“对于车费相同的到达站的距离最远的站和线路末端站点出站”。这其中的线路末端站点可以在读输入的时候完成，即只是标记下某个站点是否端点。2.下面要开始想办法去找车费相同的到达站的距离最远的站。由于涉及到距离且点数较少，所以先用floyd建图，建完距离的图之后，我们需要去找寻每个点在车费相同的到达站的最远站点，故我们还需要再建一个图（存储每个站点可到达哪些满足题意的站点）。3.建新的图的时候对于每个点都需要用到一个map来记录信息，key是当前距离对应的费用，value是该费用下的最大距离，将该点的可达点都跑一遍后再把该点能够到达的线路末端站点与满足费用下最大的距离的点存入到该点的信息中。4.搜索+剪枝：将该点能够到达的点递归搜索一遍，并在搜索过程中标记一下以便输出，而对于那些已经被标记过的点，不要重复的去搜不然可能会停不下来。
C++ 代码#include#include#include#include#includeusing namespace std;const int N = 205,INF = 0x3f3f3f3f;int n,m,k,q;int f[N][N];bool st[N],vis[N];//st用来标记是否是线路的末端，vis用来记录从某号点出发能否到达其他点vector v[N];void floyd(){for(int k=1;kdis>>aft){f[pre][aft] = f[aft][pre] = min(f[pre][aft],dis);pre = aft;if(getchar()=='\n') break;}st[aft] = true;}floyd();init_graph();cin>>q;while(q--){memset(vis,0,sizeof(vis));int be,flag = 0;cin>>be;vis[be] = 1;dfs(be,1);for(int i=1;i正文
PAT L3
算法:floyd + 搜索