深搜，剪枝。個人認為此題與棋盤其實非常相似

用一個數組記錄到達某個國家的最小距離（初值無窮大），就可以把大于等于該距離的剪枝掉（注意等于也必須減去，否則極有可能玄學錯誤）

#include<bits/stdc++.h> using namespace std; int n,k,m,s,t,ans=0x3f3f3f3f; int cou[107],cul[107][107],dis[107][107]; // 國家的文化 文化間排斥的表 國家之間的距離 bool vis[107];int jud[107]; // 已經學過的文化 到達某個國家的最小距離 void dfs(int now,int sum){ // 現在在的國家 已走的距離if(now==t){ans=min(ans,sum);return;}//到達目的地if(sum>=jud[now])return;else jud[now]=sum;//剪枝，記得要更新最小值for(int i=1;i<=n;++i){if(!vis[cou[i]]&&dis[now][i]<0x3f3f3f3f&&sum<jud[i]){//沒去過，有道路，不能夠剪枝bool flag=false;for(int j=1;j<=k;++j){if(cul[cou[i]][j]&&vis[j]){flag=true;break;}//看是否有排斥現象}if(flag)continue;//有排斥vis[cou[i]]=true;//學習文化dfs(i,sum+dis[now][i]);//下一站vis[cou[i]]=false;//記得回溯}}return; } int main(){memset(dis,0x3f,sizeof(dis));memset(cul,0,sizeof(cul));//此處建議不要設成-1，因為個人的寫法不同（if），防止有問題（數組越界了之類，雖然基本不可能，但盡量減少錯誤機會）memset(jud,0x3f,sizeof(jud));cin>>n>>k>>m>>s>>t;for(int i=1;i<=n;++i)cin>>cou[i];for(int i=1;i<=k;++i)for(int j=1;j<=k;++j)cin>>cul[i][j];for(int i=1;i<=m;++i){int u,v,d;//在循環里定義cin>>u>>v>>d;dis[u][v]=min(dis[u][v],d);//記得取小，因為可能有多條道路}vis[cou[s]]=true;//出發點的文化別忘記學dfs(s,0);if(ans!=0x3f3f3f3f)cout<<ans<<endl;else cout<<"-1"<<endl;//ans沒變，說明沒有到達return 0; }

總結

以上是生活随笔為你收集整理的洛谷 P1078 文化之旅的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。