UVA 1424 Salesmen

本文主要是介绍UVA 1424 Salesmen，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

简单dp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAX 210
using namespace std;int n,m,l,path[MAX],graph[MAX][MAX],dp[MAX][MAX];void init(){cin>>n>>m;memset(graph,0,sizeof(graph));int a,b;for(int i=0;i<m;i++){cin>>a>>b;graph[a][b]=graph[b][a]=1;}for(int i=1;i<=n;i++)graph[i][i]=1;cin>>l;for(int i=1;i<=l;i++){cin>>path[i];}memset(dp,0x7f,sizeof(dp));for(int i=1;i<=l;i++)dp[1][i]=1;dp[1][path[1]]=0;
}void solve(){for(int i=2;i<=l;i++){for(int j=1;j<=n;j++){for(int t=1;t<=n;t++){if(graph[j][t])dp[i][j]=min(dp[i][j],dp[i-1][t]+((j==path[i])?0:1));}}}int ans=0x7f7f7f7f;for(int i=1;i<=n;i++)ans=min(ans,dp[l][i]);cout<<ans<<endl;
}int main(){int T;scanf("%d",&T);while(T--){init();solve();}return 0;
}

这篇关于UVA 1424 Salesmen的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---