【NOIP2012普及组】文化之旅
;}
}
bool clash[101][101]; //读入文化是否冲突
int been[10001]; //开大一点，记录以来过的文化
int t,k,ans=INF;
bool check(int x){ //判断第x种文化是否与之前来过文化冲突for (int i=1;i<=tot;i++)if (clash[been[i]][cul[x]]) return false;return true;
}
void dfs(int x,int val){ //深搜bool f=false;if (x==t)ans=min(ans,val);if (val>=ans) return;visited[cul[x]]=true;int temp=tot;for (int i=head[x];i;i=edge[i].next){int v=edge[i].v; if (!visited[cul[v]] && !clash[cul[v]][cul[x]] && check(v) && val+edge[i].w+dist[v]//最优性剪枝been[++tot]=cul[v],f=true,dfs(v,val+edge[i].w);}tot=temp; //还原现场if (!f) visited[cul[x]]=false;
}
int main(){ios::sync_with_stdio(false);int m,s,u,v,d;cin>>n>>k>>m>>s>>t;for (int i=1;i<=n;i++)cin>>cul[i];for (int i=1;i<=k;i++)for (int j=1;j<=k;j++)cin>>clash[i][j];for (int i=1;i<=m;i++){cin>>u>>v>>d;add_edge(u,v,d);add_edge(v,u,d);}dij(n); //从终点开始跑最短路memset(visited,false,sizeof(visited));dfs(s,0); //从起点开始dfsif (ans!=INF) cout<endl; else cout<<-1<<endl;return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！