Dijkstra:
#include<iostream>
using namespace std;
dfs做法:不知道哪里错了
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int num[N],path[N];
bool book[N],vis[N];//vis剪枝需要
int g[N][N];
int n,m,s,d,minlen = INF,sum,tsum;//sum救援队数量 tsum路径条数
struct bl{
bool toend;//是否能到终点
bool renew;//有无更新路径
};
bl dfs(int x,int len,int count,int amount){//当前点,长度,第几条边,救援队数量
if(vis[x]) return {false,false};
if(x == d){
if(len < minlen){
minlen = len;
sum = amount;
tsum = count;
return {true,true};
} else if(len == minlen && sum < amount){
sum = amount;
tsum = count;
return {true,true};
}
return {true,false};
}
int point = -1;
bool toend = false;
for(int i = 0; i < n; i++){
if(!book[i] && g[i][x]!=INF && minlen >= len+g[i][x]){
book[i] = true;
bl tmp = dfs(i,len+g[i][x],count+1,amount+num[i]);
if(tmp.renew) point = i;
if(tmp.toend) toend = true;
book[i] = false;
}
}
if(point != -1) {
path[count+1] = point;
return {true,true};
} else if(toend == false){ //经过x点无法到达终点就无需再遍历
vis[x] = true;
return {false,false};
} else return{true,false};
}
int main(){
cin>>n>>m>>s>>d;
memset(g,0x3f,sizeof(g));
for(int i = 0; i < n; i++) {
cin>>num[i];
}
for(int i = 0; i < m; i++){
int u,v,w;
cin>>u>>v>>w;
g[u][v] = g[v][u] = w;
}
path[0] = s;
book[s] = true;
dfs(s,0,0,num[s]);
cout<<tsum<<' '<<sum<<endl;
for(int i = 0; i < tsum+1; i++){
if(i) cout<<' ';
cout<<path[i];
}
return 0;
}