AC版
参考大佬思路
对堆优化版的dijstra进行合题意的优化。
当出现相同距离的路径时，当前距离的路径数量加上前一个结点的路径数量。同时，判断哪条路径的救援数量会最大，更新当前结点的救援数量。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, M = N*N;
typedef pair<int,int> pii;
int h[N],e[M],ne[M],w[M],idx;
void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int dis[N];
int n,m,sx,sy;
int peo[N];
bool st[N];
int num[M],ans[N];
void heap_dij(int sx, int sy){
memset(dis,0x3f,sizeof(dis));
dis[sx] = 0;
num[sx] = 1;//最短路径的数量,题目要求最短路径数量
ans[sx] = peo[sx];
priority_queue<pii,vector<pii>,greater<pii>> heap;
heap.push({0,sx});
while(heap.size()){
pii t = heap.top();
heap.pop();
int ver = t.second;
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; i != -1; i = ne[i]){
int j = e[i];
if(dis[j] > dis[ver] + w[i]){
dis[j] = dis[ver] + w[i];
num[j] = num[ver];//最短路径的数量
ans[j] = ans[ver] + peo[j];//当点到j时，此时能召集的救援队数量
heap.push({dis[j],j});
}
else if(dis[j] == dis[ver] + w[i]){//说明出现了相同距离的路径
num[j] += num[ver];
if(ans[j] < ans[ver] + peo[j]){
ans[j] = ans[ver] + peo[j];
}
}
}
}
cout << num[sy] <<" " << ans[sy];
}
int main(){
cin >> n >> m >> sx >> sy;
if(sx > sy){
swap(sx,sy);
}
for(int i = 0; i < n; i++){
cin >> peo[i];
}
memset(h,-1,sizeof(h));
while(m--){
int a,b,c;
cin >> a >> b >> c;
add(a,b,c);
add(b,a,c);
}
heap_dij(sx,sy);
return 0;
}
10分（只过了第一个样例）
用的是堆优化的dijkstra+dfs.
思路：
首先,通过堆优化的dijkstra找到最短路径的长度。
其次，根据最短路径的长度和起点和终点，以及当前召集的救援队的人数，来进行dfs。
结果,样例过了，第一个测试点过了，其余点wa或者段错误。
没理解，自己为啥会段错误，点开了1e3,边数开了3e6
或许是我思路复杂了。
错误原因：第一个结果输出的是最短路的数量，看题不仔细，误认为是最短路径长度
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, M = N*N;
typedef pair<int,int> pii;
int h[N],e[M],ne[M],w[M],idx;
void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int dis[N];
int n,m,sx,sy;
int peo[N];
bool st[N];
int q[3*N*N];
int path;
int res;
void dfs(int u, int dist, int tot){
if(dist > path) return ;
if(dist == path && u != sy) return ;
if(u == sy){
if(dist == path){
res = max(res, tot);
return ;
}
return ;
}
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
dfs(j,dis[u] + w[i],tot + peo[j]);
}
}
void heap_dij(int sx, int sy){
memset(dis,0x3f,sizeof(dis));
dis[sx] = 0;
priority_queue<pii,vector<pii>,greater<pii>> heap;
heap.push({0,sx});
while(heap.size()){
pii t = heap.top();
heap.pop();
int ver = t.second;
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; i != -1; i = ne[i]){
int j = e[i];
if(dis[j] > dis[ver] + w[i]){
dis[j] = dis[ver] + w[i];
heap.push({dis[j],j});
}
}
}
path = dis[sy];
cout << dis[sy] <<" ";
memset(st,0,sizeof(st));
dfs(sx,dis[sx],peo[sx]);
cout << res;
}
int main(){
cin >> n >> m >> sx >> sy;
if(sx > sy){
swap(sx,sy);
}`在这里插入代码片`
for(int i = 0; i < n; i++){
cin >> peo[i];
}
memset(h,-1,sizeof(h));
while(m--){
int a,b,c;
cin >> a >> b >> c;
add(a,b,c);
add(b,a,c);
}
heap_dij(sx,sy);
return 0;
}
13分（过了第一、二个样例）
将输出结果改为：输出最短路径的数量和最大救援人数
第二个测试样例过了，其余测试样例均显示段错误
难道是dfs爆栈了？？因为无向图？？因为可能上去搜索或者往下搜索死循环了？
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, M = N*N;
typedef pair<int,int> pii;
int h[N],e[M],ne[M],w[M],idx;
void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int dis[N];
int n,m,sx,sy;
int peo[N];
bool st[N];
int path,cnt;
int res;
void dfs(int u, int dist, int tot){
if(dist > path) return ;
if(dist == path && u != sy) return ;
if(u == sy){
if(dist == path){
cnt++;
res = max(res, tot);
return ;
}
return ;
}
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
dfs(j,dis[u] + w[i],tot + peo[j]);
}
}
void heap_dij(int sx, int sy){
memset(dis,0x3f,sizeof(dis));
dis[sx] = 0;
priority_queue<pii,vector<pii>,greater<pii>> heap;
heap.push({0,sx});
while(heap.size()){
pii t = heap.top();
heap.pop();
int ver = t.second;
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; i != -1; i = ne[i]){
int j = e[i];
if(dis[j] > dis[ver] + w[i]){
dis[j] = dis[ver] + w[i];
heap.push({dis[j],j});
}
}
}
path = dis[sy];
dfs(sx,dis[sx],peo[sx]);
cout <<cnt <<" " << res;
}
int main(){
cin >> n >> m >> sx >> sy;
for(int i = 0; i < n; i++){
cin >> peo[i];
}
memset(h,-1,sizeof(h));
while(m--){
int a,b,c;
cin >> a >> b >> c;
add(a,b,c);
add(b,a,c);
}
heap_dij(sx,sy);
return 0;
}
