HDU 5418 Victor and World(상압 dp, 최단거리)

1738 단어
우선 Folyd로 임의의 두 점 사이의 최단로를 구하세요.
그리고 dp[i][S]에 방문 상황을 S로 표시하고 마지막으로 i 국가를 방문하는 데 가장 적은 비용을 쓴다.
전이 방정식은 dp[i][S|(1#pragma warning(disable:4996) #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int mp[17][17]; int dp[17][1 << 16];//dp[i][S] i, S int main(){ //freopen("in.txt", "r", stdin); int t; scanf("%d", &t); while (t--){ int n, m; scanf("%d %d", &n, &m); memset(mp, 0x3f, sizeof mp); for (int i = 0; i < m; i++){ int u, v, c; scanf("%d %d %d", &u, &v, &c); mp[u][v] = mp[v][u] = min(mp[u][v], c); } for (int i = 1; i <= n; i++)mp[i][i] = 0; for (int k = 1; k <= n; k++){ for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++){ mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]); } } } memset(dp, 0x3f, sizeof dp); dp[1][1] = 0; for (int i = 1; i < (1 << n); i++){//zhuang tai for (int j = 1; j <= n; j++){//qi dian if (i&(1 << (j - 1))){ for (int k = 1; k <= n; k++){//zhong dian if ((i&(1 << (k - 1))) == 0){ dp[k][i | (1 << (k - 1))] = min(dp[k][i | (1 << (k - 1))], dp[j][i] + mp[j][k]); } } } } } int ans = 0x3f3f3f3f; for (int i = 2; i <= n; i++){ ans = min(ans, dp[i][(1 << n) - 1] + mp[i][1]); } if (n == 1)ans = 0; printf("%d
", ans); } return 0; }

좋은 웹페이지 즐겨찾기