学步园

多种写法。渣渣只会dfs

#include <cstdio>
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
#define INF 99999999
int const MAXN = 20;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int va[MAXN],va1[MAXN],maze[MAXN][MAXN],vis[MAXN];
int n,m,t,ans;
int s,e;
inline int Max(int a,int b){
    return a>b?a:b;
}
inline int Min(int a,int b){
    return a<b?a:b;
}
void Dfs(int st,int step,int vl){
    if(st == e && step <= t){
        ans = Max(ans,vl);
        return ;
    }
    for(int i = 0;i < n;i++){
        if(maze[st][i] == INF || vis[i]) continue;
        if(step + maze[st][i] > t) continue;
        vis[i] = 1;
        Dfs(i,step + maze[st][i],vl + va[i]);
        vis[i] = 0;
    }
    return ;
}
void Init(){
    for(int i = 0;i < MAXN;i++){
        for(int j = 0;j < MAXN;j++){
            maze[i][j] = INF;
        }
    }
    memset(vis,0,sizeof(vis));
    memset(va,0,sizeof(va));
    ans = -1;
}
int main(){
    while(~scanf("%d%d%d",&n,&m,&t)){
        Init();
        scanf("%d%d",&s,&e);
        for(int i = 0;i < n;i++){
            scanf("%d",&va[i]);
        }
        for(int i = 0;i < m;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            maze[a][b] = maze[b][a] = Min(maze[b][a],c);
        }
        for(int k = 0;k < n;k++){
            for(int i = 0;i < n;i++){
                for(int j = 0;j < n;j++){
                    maze[i][j] = Min(maze[i][j],maze[i][k] + maze[k][j]);
                }
            }
        }
        int vl = va[s];
        va[s] = 0;
        Dfs(s,0,vl);
        if(ans == -1)printf("0\n");
        else printf("%d\n",ans);
    }
    return 0;
}
/*
3 3 5
0 1
0 1 1
0 1 1
1 2 2
0 2 10

*/