追债之旅 爆搜加剪枝你值得拥有

上面是爆搜+剪枝
下面是正解

爆搜加剪枝你值得拥有。

if(sum>=ans) return;
if(sum>=ans) return;
if(sum>=ans) return;

对加了这句话，就ok了。
爆搜的代码也不需要多解释了，今天突然想起来剪枝一下好像可以就试了试。
其实就是dfs暴力所有路径。。。加了一个再普通不过的剪枝。

代码：

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define endl '\n'
#define ios std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
//#define int long long
const int maxn = 2e4+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9+7;
using namespace std;

bool visited[1010];
struct wazxy{
    int to,w,next;
}edge[maxn];
int head[maxn],cnt=1;
int n,m,k;
int p[maxn],ans;
inline void add(int u,int v,int w){
    edge[cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void dfs(int x,int sum,int d){
    if(x==n){
        ans=min(ans,sum);
        return ;
    }
    if(sum>=ans) return;
    if(d>k-1) return;
    for(int i=head[x];i;i=edge[i].next){
        if(!visited[edge[i].to]){
            visited[edge[i].to]=true;
            dfs(edge[i].to,sum+edge[i].w+p[d],d+1);
            visited[edge[i].to]=false;
        }
    }
}
int main(){
    ios
    cin>>n>>m>>k;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=0;i<k;i++){
        cin>>p[i];
    }
    memset(visited,false,sizeof visited);
    ans=MaxN;
    dfs(1,0,0);
    if(ans==MaxN) cout<<-1;
    else cout<<ans<<endl;
    return 0;

}