# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
538174 | 2022-03-16T07:29:53 Z | 79brue | Mountains and Valleys (CCO20_day1problem3) | C++14 | 5 ms | 696 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, m; int dist[22][22]; int DP[1048576][20]; vector<int> link[5002]; queue<pair<int, int> > que; bool visited[5002]; int main(){ scanf("%d %d", &n, &m); if(n>3){ for(int i=1; i<=m; i++){ int x, y, c; scanf("%d %d %d", &x, &y, &c); if(c==1){ link[x].push_back(y); link[y].push_back(x); } } que.push(make_pair(1, 0)); visited[1] = 1; int nxt = 0, dst=0; while(!que.empty()){ auto tmp = que.front(); que.pop(); nxt = tmp.first; dst = tmp.second; for(auto x: link[tmp.first]){ if(visited[x]) continue; visited[x] = 1; que.push(make_pair(x, tmp.second+1)); } } memset(visited, 0, sizeof(visited)); nxt = dst = 0; que.push(make_pair(nxt, 0)); visited[nxt] = 1; while(!que.empty()){ auto tmp = que.front(); que.pop(); nxt = tmp.first; dst = tmp.second; for(auto x: link[tmp.first]){ if(visited[x]) continue; visited[x] = 1; que.push(make_pair(x, tmp.second+1)); } } printf("%d", 2*n-2-dst); return 0; } for(int i=0; i<=n; i++){ for(int j=0; j<=n; j++){ dist[i][j] = 1e9; } } for(int i=1; i<=m; i++){ int x, y, c; scanf("%d %d %d", &x, &y, &c); dist[x][y] = dist[y][x] = c; } for(int k=0; k<n; k++){ for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } for(int i=0; i<(1<<n); i++) for(int j=0; j<=n; j++) DP[i][j] = 1e9; for(int i=0; i<n; i++) DP[(1<<i)][i] = 0; for(int d=1; d<(1<<n); d++){ for(int i=0; i<n; i++){ if((d>>i)&1){ // printf("%d %d: %d\n", d, i, DP[d][i]); for(int j=0; j<n; j++){ DP[(d|(1<<j))][j] = min(DP[(d|(1<<j))][j], DP[d][i] + dist[i][j]); } } } } int ans = 1e9; for(int i=0; i<n; i++) ans = min(ans, DP[(1<<n)-1][i]); printf("%d", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 696 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |