题解 P2349 【金字塔】

zhenglier · 2018-12-20 15:50:41 · 题解

本人不会A*,也不会枚举最大值跑dijkstra。所以就用暴力搜索过了这道题。

搜索传四个参数，上一个到的点，当前点，当前路径最大值，当前走过的长度。

这里做两个剪枝，一个是不会回到上一个节点，一个是如果当前走过的长度加上当前路径最大值如果大于现在答案，直接回溯。

然后就可以用复杂度玄学的搜索过了此题了。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int tot=1,head[110],bian[4010],nxt[4010],zhi[4010];
inline void add(int x,int y,int z){
    tot++,bian[tot]=y,zhi[tot]=z,nxt[tot]=head[x],head[x]=tot;
}
int ans=1e9;
void dfs(int from,int x,int mx,int sum){
    if(sum+mx>ans)return;
    if(x==n){
        ans=min(sum+mx,ans);
        return;
    }
    for(int i=head[x];i;i=nxt[i]){
        int y=bian[i];
        if(y==from)continue;
        dfs(x,y,max(mx,zhi[i]),sum+zhi[i]);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    dfs(0,1,0,0);
    cout<<ans<<endl;
}