#include<algorithm>
#include<fstream>
#include<functional>
#include<iostream>
using namespace std;
static const int N=;
typedef long long int64;
struct node
{
int v,w;
node *next;
}alist[*N];
struct heapnode
{
int64 w;
int u;
bool operator>(const heapnode &r)const
{
return w>r.w;
}
};
int p[N][];
int64 w[N][];
void dfs1(int u)
{
for(node *i=alist[u].next;i;i=i->next)
if(i->v!=p[u][])
{
p[i->v][]=u;
w[i->v][]=i->w;
dfs1(i->v);
}
}
bool visit[N];
void dfs2(int u)
{
if(visit[u])return;
if(!alist[u].next->next)return;
visit[u]=true;
for(node *i=alist[u].next;i;i=i->next)
if(i->v!=p[u][])
{
dfs2(i->v);
if(!visit[i->v])
{
visit[u]=false;
break;
}
}
}
int main()
{
ifstream fin("blockade.in");
ofstream fout("blockade.out");
int n(),m();
fin>>n;
node *anode(alist+n+);
for(int i=;i<n-;i++)
{
int u(),v(),ww();
fin>>u>>v>>ww;
anode->v=v;
anode->w=ww;
anode->next=alist[u].next;
alist[u].next=anode++;
anode->v=u;
anode->w=ww;
anode->next=alist[v].next;
alist[v].next=anode++;
}
fin>>m;
static int d[N];
for(int i=;i<m;i++)
fin>>d[i];
int NScount=;
for(node *i=alist[].next;i;i=i->next)
{
NScount++;
p[i->v][]=;
w[i->v][]=i->w;
dfs1(i->v);
}
if(NScount>m)
{
fout<<"-1"<<endl;
return ;
}
for(int j=;j<=;j++)
for(int i=;i<=n;i++)
{
p[i][j]=p[p[i][j-]][j-];
w[i][j]=w[i][j-]+w[p[i][j-]][j-];
}
static heapnode a[N],b[N];
heapnode *atop(),*aback(),*btop(),*bback();
static int _w[N];
for(node *i=alist[].next;i;i=i->next)
_w[i->v]=i->w;
int64 l(),r(1e16),ans(1e16);
greater<heapnode> comp;
while(l<=r)
{
atop=a;
aback=a;
btop=b;
bback=b;
int64 mm=(l+r)>>;
for(int i=;i<=n;i++)
visit[i]=false;
for(int i=;i<m;i++)
{
int u=d[i];
int64 ww=mm;
for(int j=;j>=;j--)
if(p[u][j]&&p[u][j]!=&&ww>=w[u][j])
{
ww-=w[u][j];
u=p[u][j];
}
if(/*p[u][0]==1&&*/ww>w[u][])
{
aback->w=ww-w[u][];
aback->u=u;
aback++;
push_heap(atop,aback,comp);
}
else visit[u]=true;
}
dfs2();
if(visit[])
{
ans=mm;
r=mm-;
}
else
{
for(node *i=alist[].next;i;i=i->next)
if(!visit[i->v])
{
bback->w=i->w;
bback->u=i->v;
bback++;
push_heap(btop,bback,comp);
}
while(btop!=bback||atop!=aback)
{
while(atop!=aback&&!visit[atop->u]&&atop->w<_w[atop->u])
{
visit[atop->u]=true;
pop_heap(atop,aback,comp);
aback--;
}
while(btop!=bback&&visit[btop->u])
{
pop_heap(btop,bback,comp);
bback--;
}
if(btop==bback||atop==aback)break;
if(atop->w>=btop->w)
{
visit[btop->u]=true;
pop_heap(atop,aback,comp);
aback--;
pop_heap(btop,bback,comp);
bback--;
}
else
{
pop_heap(atop,aback,comp);
aback--;
}
}
if(btop==bback)
{
ans=min(ans,mm);
r=mm-;
}
else l=mm+;
}
}
fout<<ans<<endl;
return ;
}

最新文章

  1. QT 默认环境路径配置方法
  2. springmvc参数绑定
  3. R语言画图实例-参考R语言实战
  4. 《SQL Server企业级平台管理实践》读书笔记——SQL Server数据库文件分配方式
  5. @错误抑制运算符和or die()
  6. QListWidgetItem带上颜色的问题
  7. java程序执行时,JVM内存
  8. EntityFramework经典的left join语法
  9. Java集合初体验
  10. js如何判断一个变量是否是数组?
  11. 列举至少3种Support包中提供的布局或工具
  12. Windows上SQLPLUS的设置
  13. DevExpress--TreeList节点添加图片
  14. SQL优化思路大全
  15. java.lang.ClassNotFoundException: org.hibernate.engine.FilterDefinition的解决方案
  16. 梯度下降法、牛顿法、高斯牛顿法、LM最优化算法
  17. golang 自定义json解析
  18. navicat创建存储过程的小问题
  19. LINUX网络之ifconfig命令与ping
  20. 20170708xlVBA添加新产品修改公式

热门文章

  1. leetcode14
  2. delphi 路径函数
  3. Javascript 日期 加减
  4. C++Builder 内存泄露检测
  5. 文件上传:input file FileReader
  6. springboot中端点监管 endpoint actuator
  7. 全球数据库--&gt;基金/管理产品--&gt;分类/行业平均--&gt;开放式分类
  8. BETTER SUPPORT FOR FUNCTIONAL PROGRAMMING IN ANGULAR 2
  9. AngularJs2.0
  10. 【转】java.sql.SQLException: statement is closed语句被关闭 druid连接池报错