Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
67815 | Ender | 炸弹 | C++ | 运行超时 | 20 | 1000 MS | 272 KB | 1108 | 2023-01-19 17:23:52 |
#include <iostream> #include <cstdio> using namespace std; const int N = 2005; int od[N],a[N],b[N],n,c; long long ans = 1000000000000000000; bool vis[N]; inline int abs(int x) { if(x < 0) return -x; return x; } inline long long Dis(int x,int y,int xx,int yy) { if(y == yy) return abs(x - xx); else return abs(x) + abs(xx) + abs(y - yy); } void solve() { long long res = 0; for(int i = 1;i <= c;i++) if(b[od[i]] < b[od[i - 1]]) return; for(int i = 1;i <= c;i++) res+=Dis(a[od[i - 1]],b[od[i - 1]],a[od[i]],b[od[i]]); ans = min(ans,res); } void DFS(int k) { if(k == c + 1) { /*for(int i = 1;i <= c;i++) cout<<od[i]<<' '; cout<<endl;*/ solve(); return; } for(int i = 1;i <= n;i++) { if(!vis[i]) { od[k] = i; vis[i] = 1; DFS(k + 1); vis[i] = 0; } } } int main() { //freopen("boom.in","r",stdin); //freopen("boom.out","w",stdout); int i; cin>>n; for(i = 1;i <= n;i++) cin>>a[i]>>b[i]; for(i = 1;i <= n;i++) { ans = 1000000000000000000; c = i; DFS(1); cout<<ans<<endl; } return 0; }