暴搜法
首先声明：本人蒟蒻，题解的bug一片一片，敬请见谅。
废话不多说，开始思路。显而易见的，此题可以深搜。不知当时脑子有什么问题，立刻蹦出一个伟大错炸的想法：根据小奥最短路径，只能向下或向右走，不可向上或向左走，这会导致金钱增多。
于是就自然想到搜索下、下下、右、右右
见代码：
#include <iostream> #include<cmath> using namespace std; int m,n,x,y,z,num=0,max1=99999; bool flag=true,s=true; int a[1001][1001]; int search(int,int); int main() { cin>>m>>n; for(int i=1;i<=n;i++) { cin>>x>>y>>z; a[x][y]=(z+1); } if(m!=1) search(1,1); else { cout<<0; return 0; } if(max1!=99999) cout<<max1; else cout<<-1; return 0; } int search(int h,int l) { if(h==m&&l==m) { if(max1>num) max1=num; } if(a[h][l+1]!=0) { num+=abs(a[h][l+1]-a[h][l]); flag=true; search(h,l+1); num-=abs(a[h][l+1]-a[h][l]); flag=false; } if(a[h+1][l]!=0) { num+=abs(a[h+1][l]-a[h][l]); flag=true; search(h+1,l); num-=abs(a[h+1][l]-a[h][l]); if(s==false) flag=false; } if(a[h][l+2]!=0&&flag==true) { flag=false; num+=2+abs(a[h][l+2]-a[h][l]); s=false; search(h,l+2); flag=true; s=true; num-=2+abs(a[h][l+2]-a[h][l]); } if(a[h+2][l]!=0&&flag==true) { flag=false; s=false; num+=2+abs(a[h+2][l]-a[h][l]); search(h+2,l); flag=true; s=true; num-=2+abs(a[h+2][l]-a[h][l]); } if(a[h+1][l+1]!=0&&flag==true) { flag=false; s=false; num+=2+abs(a[h+1][l+1]-a[h][l]); search(h+1,l+1); flag=true; s=true; num-=2+abs(a[h+1][l+1]-a[h][l]); } }
可惜只拿到10分……
好歹样例过了！开心。
暴搜法2
然后在正常大脑的思考下，得到了正确的想法：如果说……只有一条路的话呢？弯弯绕绕扭七扭八，还不是要走？
于是新的思路出现了，搜索总共12个方向。
代码总体与上面差不多，就不放了。可是……分数又低了。5分！
当然这是正常的，12个方向，不死才有鬼呢！上面是全体WA，这是全体TLE。
暴搜法3
后来，惊奇地发现，只搜四个方向即可，设布尔变量储蓄魔法，有颜色就走，没颜色就用魔法，用过后就搜下一个。
见代码：
#include <iostream>
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; int m,n,x1,y2,k3,ans=0x3f3f3f,a[1001][1001],f[1001][1001]; int p[5]={0,-1,1,0,0},y[5]={0,0,0,-1,1}; void dfs(int h,int l,int sum,bool flag) { if(a[h][l]==0) return ; if(sum>=f[h][l]) return ; f[h][l]=sum; if(h==m&&l==m) { ans=min(sum,ans); return ; } for(int i=1;i<=4;i++) { if(a[h+p[i]][l+y[i]]!=0) { dfs(h+p[i],l+y[i],sum+abs(a[h+p[i]][l+y[i]]-a[h][l]),true); } else { if(flag==true) { a[h+p[i]][l+y[i]]=a[h][l]; dfs(h+p[i],l+y[i],sum+2,false); a[h+p[i]][l+y[i]]=0; } } } } int main() { memset(f,0x3f3f3f,sizeof(f)); scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&x1,&y2,&k3); a[x1][y2]=k3+1; } dfs(1,1,0,true); if(ans!=0x3f3f3f) printf("%d",ans); else printf("-1"); return 0; }