标签：minn 比特 int long 100005 cc while 跳跃
- 这次真的是差五分钟就能过掉这题了，好可惜呀
- 二进制数位的包含关系构成一颗树，我们可以在这棵树上DP来统计一些信息
- 十五分钟加上这样一个DP，未必来不及。只是，越到时间紧张的关头，越要屏蔽其他念想的干扰，告诉自己不去管时间，把注意力集中在代码的编写上
- 如果你写完代码能一遍过，那时间往往是来得及的
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int>a[100005];
vector<int>c[100005];
priority_queue<pair<long long,int> >q;
long long d[100005],g[100005];
bool f[100005];
int read1()
{
char cc=getchar();
while(!(cc>=48&&cc<=57))
{
if(cc=='-')
{
break;
}
cc=getchar();
}
bool f=false;
int s=0;
if(cc=='-')
{
f=true;
}
else
{
s=cc-48;
}
while(1)
{
cc=getchar();
if(cc>=48&&cc<=57)
{
s=s*10+cc-48;
}
else
{
break;
}
}
if(f==true)
{
s=-s;
}
return s;
}
void dijkstra()
{
int cnt=0;
while(cnt<n&&!q.empty())
{
int p=q.top().second;
long long va=-q.top().first;
q.pop();
if(f[p]==true||va!=d[p])
{
continue;
}
f[p]=true;
cnt++;
for(int i=0;i<a[p].size();i++)
{
if(d[p]+c[p][i]<d[a[p][i]])
{
d[a[p][i]]=d[p]+c[p][i];
q.push(make_pair(-d[a[p][i]],a[p][i]));
}
}
}
}
long long dp(int x)
{
if(g[x]!=-1)
{
return g[x];
}
if(x==(x&(-x)))
{
return g[x]=d[x];
}
long long minn=LLONG_MAX;
for(int i=0;i<17;i++)
{
if(((x>>i)&1)==1)
{
minn=min(minn,dp(x&(~(1<<i))));
}
}
return g[x]=minn;
}
int main()
{
int T;
cin>>T;
while(T--)
{
long long k;
cin>>n>>m>>k;
while(!q.empty())
{
q.pop();
}
for(int i=1;i<=n;i++)
{
a[i].clear();
c[i].clear();
f[i]=false;
d[i]=LLONG_MAX;
g[i]=-1;
}
for(int i=1;i<=m;i++)
{
int u,v,w;
u=read1();
v=read1();
w=read1();
a[u].push_back(v);
a[v].push_back(u);
c[u].push_back(w);
c[v].push_back(w);
}
d[1]=0;
q.push(make_pair(-d[1],1));
dijkstra();
for(int i=1;i<=n;i++)
{
dp(i);
}
while(!q.empty())
{
q.pop();
}
d[1]=0;
q.push(make_pair(-d[1],1));
f[1]=false;
for(int i=2;i<=n;i++)
{
f[i]=false;
if(g[i]!=LLONG_MAX)
{
d[i]=min(g[i]+k*i,k*(1|i));
}
else
{
d[i]=k*(1|i);
}
q.push(make_pair(-d[i],i));
}
dijkstra();
for(int i=2;i<=n;i++)
{
printf("%lld ",d[i]);
}
cout<<endl;
}
return 0;
}
标签：minn,
比特,
int,
long,
100005,
cc,
while,
跳跃
From： https://www.cnblogs.com/watersail/p/18326141