本题的背景是求定点和定点之间的最短路问题（所有的最短路 不是一个解 是全部解，方法手段来自数据结构课程中的迪杰斯特拉算法和dfs（深度优先遍历）。
分别用两种方法编程如下代码
- dfs
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define maxv 510
bool visit[maxv]; int arc[maxv][maxv];//邻接矩阵 int M,N,C1,C2; //M总顶点数，N总边数，C1起点，C2终点 int vex[maxv]; //记录每个顶点的救援人数 int mind=0xfffffff,maxr=0,cnt;//mind最短路径，maxr最大救援人数，cnt最短路径条数 void dfs(int st,int end,int curPath,int curRes){
if (st==end){
if (curPath<mind){
cnt=1;
mind=curPath;
maxr=curRes;
}else if(curPath==mind){
cnt++;
if (curRes>maxr)
maxr=curRes;
}
return;
}
else{
for (int k=0;k<M;k++){
if (arc[st][k]!=0&&!visit[k]){
visit[k]=1;
dfs(k,end,curPath+arc[st][k],curRes+vex[k]);
visit[k]=0;
}
}
return ;
}
}
int main(){
while(scanf("%d%d%d%d",&M,&N,&C1,&C2)!=EOF){
memset(arc,0,sizeof(arc));
for(int i=0;i<M;i++)
scanf("%d",&vex[i]);
int i,j,d;
for(int k=0;k<N;k++){
scanf("%d%d%d",&i,&j,&d);
arc[j][i]=arc[i][j]=d;
}
memset(visit,0,sizeof(visit));
visit[C1]=1;
dfs(C1,C2,0,vex[C1]);
printf("%d %d",cnt,maxr);
}
return 0;
}
- 容易放的错误是mind,maxr忘记赋初始值
- 矩阵scanf输入的时候&arg[i][j] 不会报错 但会导致输入异常 这个问题我也很奇怪 先在这里记录说明了
- 迪杰斯特拉算法
#include <iostream>
#include <cstdio>
using namespace std;
#define maxv 510
#define inf 65536 int arc[maxv][maxv];//邻接矩阵 int M,N,C1,C2; //M总顶点数，N总边数，C1起点，C2终点 int vex[maxv]; //记录每个顶点的救援人数 int maxr=0,cnt;//mind最短路径，maxr最大救援人数，cnt最短路径条数 int Path[maxv],D[maxv],S[maxv];
//Path[]记录从源点v0到终点vi的直接前驱顶点序号
//D[]记录从源点v0到终点vi的当前最短路径长度
//S[]记录从源点v0到源点vi是否已经被确定最短路径长度 /*计算v0到j的当前最大救援人数*/
void compute(int v0,int j){
int curRes=vex[v0];
for (int k=j;k!=v0;k=Path[k]){
curRes+=vex[k];
}
if (curRes>maxr)
maxr=curRes;
return;
} void dijistra(int v0,int v){
int mind,w;
//mind最短路径 w被加入到S中的顶点序号 int curRes=0;
/*初始化*/
for (int i=0;i<M;i++){
S[i]=false;
D[i]=arc[v0][i];
if (D[i]<inf)
Path[i]=v0;
else
Path[i]=-1;
}
cnt=1;
compute(v0,v);
S[v0]=true;
D[v0]=0; /*v0到其他M-1个顶点的最短路径*/
for (int i=1;i<M;i++){
mind=inf;
for (int j=0;j<M;j++)
if (!S[j]&&D[j]<mind){
w=j;mind=D[j];
}
S[w]=true;
for (int j=0;j<M;j++)
if (!S[j]&&(D[w]+arc[w][j]<D[j])){
D[j]=D[w]+arc[w][j];
Path[j]=w;
if (j==v){
cnt=1;
maxr=0;
compute(v0,j);
}
}else if (!S[j]&&D[w]+arc[w][j]==D[j]){
Path[j]=w;
if (j==v){
cnt++;/*v0到顶点j的当前最短路径不止一条*/
compute(v0,j);
}
}
}
return;
}
int main(){
while(scanf("%d%d%d%d",&M,&N,&C1,&C2)!=EOF){
for (int i=0;i<M;i++)
for (int j=0;j<M;j++)
arc[i][j]=inf;
for(int i=0;i<M;i++)
scanf("%d",&vex[i]);
int i,j,d;
for(int k=0;k<N;k++){
scanf("%d%d%d",&i,&j,&d);
arc[j][i]=arc[i][j]=d;
}
dijistra(C1,C2);
printf("%d %d\n",cnt,maxr);
//printf("%d %d %d %d %d\n",cnt,maxr,D[C2],Path[C2],Path[Path[C2]]);
/*for (int i=0;i<M;i++){
for (int j=0;j<M;j++)
printf("%d ",arc[i][j]);
printf("\n");
}*/
}
return 0;
}
这段代码目前只能通过pat平台的三个测试样例 得 16分 后续会 改bug