Wow! Such Conquering!

Problem Description

There are n Doge Planets in the Doge Space. The conqueror of Doge Space is Super Doge, who is going to inspect his Doge Army on all Doge Planets. The inspection starts from Doge Planet 1 where DOS (Doge Olympic Statue) was built. It takes Super Doge exactly Txy time to travel from Doge Planet x to Doge Planet y.
With the ambition of conquering other spaces, he would like to visit all Doge Planets as soon as possible. More specifically, he would like to visit the Doge Planet x at the time no later than Deadlinex. He also wants the sum of all arrival time of each Doge Planet to be as small as possible. You can assume it takes so little time to inspect his Doge Army that we can ignore it.

Input

There are multiple test cases. Please process till EOF.
Each test case contains several lines. The first line of each test case contains one integer: n, as mentioned above, the number of Doge Planets. Then follow n lines, each contains n integers, where the y-th integer in the x-th line is Txy . Then follows a single line containing n - 1 integers: Deadline2 to Deadlinen.
All numbers are guaranteed to be non-negative integers smaller than or equal to one million. n is guaranteed to be no less than 3 and no more than 30.

Output

If some Deadlines can not be fulfilled, please output “-1” (which means the Super Doge will say “WOW! So Slow! Such delay! Much Anger! . . . ” , but you do not need to output it), else output the minimum sum of all arrival time to each Doge Planet.

Sample Input

4
0 3 8 6
4 0 7 4
7 5 0 2
6 9 3 0
30 8 30
4
0 2 3 3
2 0 3 3
2 3 0 3
2 3 3 0
2 3 3

Sample Output

36
-1
暴力搜索,剪枝

view code#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define FOR(i,s,t) for(int i=(s); i<=(t); i++)
const int INF = 1<<30;
const int N = 35;
int dist[N][N], tm[N], n;
int bit[N], tot, ans; void floyd()
{
REP(k,n) REP(i,n) REP(j,n) dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
} void dfs(int u, int s, int cost, int sum, int num)
{
if(sum>=ans) return ;
if(s == tot){
ans = min(ans, sum);
return ;
}
FOR(i,1,n-1){
if(s&bit[i]) continue;
if(cost+dist[u][i]>tm[i]) return ;
}
FOR(i,1,n-1){
if(s&bit[i]) continue;
dfs(i, s|bit[i], cost+dist[u][i], sum+num*dist[u][i], num-1);
}
} void solve()
{
REP(i,n) REP(j,n) scanf("%d", &dist[i][j]);
floyd();
FOR(i,1,n-1) scanf("%d", tm+i);
ans = INF, tot = bit[n]-1;
dfs(0, 1, 0, 0, n-1);
if(ans==INF) ans=-1;
printf("%d\n",ans);
} int main()
{
// freopen("in.txt", "r", stdin);
REP(i,31) bit[i] = 1<<i;
while(scanf("%d", &n)>0) solve();
return 0;
}

最新文章

  1. Angular2 小贴士 Name
  2. 分享一个php邮件库——swiftmailer
  3. ACM-JAVA基础
  4. MySQL and Postgres command equivalents (mysql vs psql)
  5. java为什么要设置环境变量
  6. 在linux下修改mysql的root密码
  7. CSS3 动画记
  8. Kettle中通过触发器方式实现数据 增量更新
  9. ActiveX控件打包成Cab实现浏览器自动下载安装
  10. Mybatis分页插件PageHelper正确的使用方法(网上有2篇不够科学的文章)
  11. HDU 5242 Game(三个贪心)
  12. DDOS学习笔记(《破坏之王-DDOS攻击与防范深度剖析》)
  13. Perl多线程(1):解释器线程的特性
  14. linux----------yum一些安装命令汇总
  15. python正则表达式(四)
  16. 使用idea生成maven项目的jar包(转)
  17. Spring Boot学习笔记:整合Shiro
  18. c#批量更新list对象sql
  19. 将DataTable 覆盖到 SQL某表(包括表结构及所有数据)
  20. ACL授权实例

热门文章

  1. java 线程 Lock 锁使用Condition实现线程的等待(await)与通知(signal)
  2. 详解Javascript的继承实现(二)
  3. 25 BasicUsageEnvironment0基本使用环境基类——Live555源码阅读(三)UsageEnvironment
  4. mysql随机获取一条或者多条数据
  5. Edmond_Karp算法
  6. 最最简单的~WordCount&#172;
  7. poj 1005 I Think I Need a Houseboat
  8. Node安装与环境配置
  9. HTML 5结构
  10. ucos事件邮箱信号量队列详解
  11. 如何写一个jquery插件
  12. mac安装mysql的两种方法(含配置)
  13. .Net core使用Autofac进行依赖注入示例
  14. 跨平台 webapp 开发技术之 Hybrid App
  15. 08-webpack的介绍
  16. PCR技术
  17. C#中利用LightningChart绘制曲线图表
  18. 【转】WinForm基础
  19. Java集合——LinkedList源码详解
  20. 理解学习Springboot(一)