题目
PAT 甲级 1003 Emergency (25分) 图论：最短路径
思路
dijkstra 找到所有最短路 dfs 筛选聚集医疗人员最多的路线
题解
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std
;
const int maxn
= 510;
const int INF
=0x7fffffff;
int rts
[maxn
];
int g
[maxn
][maxn
];
int dist
[maxn
],vis
[maxn
],maxh
,minds
;
vector
<int> pre
[maxn
],temp
,ans
;
int n
,m
,c1
,c2
;
void dfs(int v
){
if(v
==c1
){
minds
++;
temp
.push_back(v
);
int hands
=0;
for(int i
=temp
.size()-1;i
>=0;i
--){
hands
+=rts
[temp
[i
]];
}
if(maxh
<hands
){
maxh
=hands
;
ans
= temp
;
}
temp
.pop_back();
}
temp
.push_back(v
);
for(int i
=0;i
<pre
[v
].size();i
++){
dfs(pre
[v
][i
]);
}
temp
.pop_back();
}
void dijkstra(int v
){
fill(dist
,dist
+maxn
,INF
);
fill(vis
,vis
+maxn
,0);
dist
[v
]=0;
for(int i
=0;i
<n
;i
++){
int mini
=-1,min
=INF
;
for(int j
=0;j
<n
;j
++){
if(vis
[j
]==1)continue;
if(dist
[j
]<min
){
min
=dist
[j
];
mini
=j
;
}
}
if(mini
==-1||mini
==c2
)break;
vis
[mini
]=1;
for(int j
=0;j
<n
;j
++){
if(g
[mini
][j
]==0||vis
[j
]==1)continue;
if(g
[mini
][j
]+dist
[mini
]<dist
[j
]){
dist
[j
]=g
[mini
][j
]+dist
[mini
];
pre
[j
].clear();
pre
[j
].push_back(mini
);
}else if(g
[mini
][j
]+dist
[mini
]==dist
[j
]){
pre
[j
].push_back(mini
);
}
}
}
}
int main(int argc
,char * argv
[]){
int l
,d
,a
;
scanf("%d%d%d%d",&n
,&m
,&c1
,&c2
);
for(int i
=0;i
<n
;i
++){
scanf("%d",&rts
[i
]);
}
for(int i
=0;i
<m
;i
++){
scanf("%d %d %d",&d
,&a
,&l
);
g
[a
][d
]=g
[d
][a
]=l
;
}
dijkstra(c1
);
dfs(c2
);
printf("%d %d",minds
,maxh
);
return 0;
}
