UVALive 4256 Salesmen——dp

UVALive 4256 Salesmen——dp

#include #include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;int T, n, m, L, a[210];vector G[110];int dp[210][110];//递推到第i个数，将其改为j的最小花费void init() { for (int i = 1; i <= n; i++) G[i].clear();}void solve() { scanf("%d %d", &n, &m); init(); int u, v; for (int i = 1; i <= m; i++) { scanf("%d %d", &u, &v); G[u].push_back(v); G[v].push_back(u); } scanf("%d", &L); for (int i = 1; i <= L; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) dp[0][i] = 0; for (int i = 1; i <= L; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = INF; int cost = (a[i] != j); //相同 dp[i][j] = min(dp[i][j], dp[i-1][j] + cost); //边 for (int k = 0; k < G[j].size(); k++) { dp[i][j] = min(dp[i][j], dp[i-1][G[j][k]] + cost); } } } int ans = INF; for (int i = 1; i <= n; i++) ans = min(dp[L][i], ans); printf("%d\n", ans);}int main() { scanf("%d", &T); while (T--) solve(); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。