网站备案有什么坏处,月子会所 网站源码,永久免费做网站app,开发一个电商app需要多少钱正题
题目链接:https://ac.nowcoder.com/acm/contest/1104/B 题目大意 nnn个点mmm条边的无向图#xff0c;kkk条必须经过的边#xff0c;求从1出发经过这kkk条边再回到1的最短路。 解题思路
我们每条边两段的端点和1是我们需要用到的特征点#xff0c;我们用计算出每个特征…正题
题目链接:https://ac.nowcoder.com/acm/contest/1104/B 题目大意
nnn个点mmm条边的无向图kkk条必须经过的边求从1出发经过这kkk条边再回到1的最短路。 解题思路
我们每条边两段的端点和1是我们需要用到的特征点我们用计算出每个特征点的之间的最短距离然后开始dpdpdp。
gi,jg_{i,j}gi,j表示经过的必经边的状态为iii在第jjj个特征点的最短路然后枚举转移即可。
时间复杂度O(knlogn2k∗k2)O(kn\log n2^k*k^2)O(knlogn2k∗k2) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define ll long long
using namespace std;
const ll N51000;
struct edge_node{ll to,next,w;
}a[N*8];
struct node{ll num,w;
};
bool operator (node x,node y)
{return x.wy.w;}
priority_queuenode q;
ll n,m,k,tot,ans1e19,cnt,MS;
ll ls[N],f[26][N],g[4096][26],p[26];
bool v[N];
void addl(ll x,ll y,ll w)
{a[tot].toy;a[tot].nextls[x];a[tot].ww;ls[x]tot;
}
void dij(ll num,ll s)
{memset(v,0,sizeof(v));q.push((node){s,0});f[num][s]0;while(!q.empty()){ll xq.top().num,wq.top().w;q.pop();if(v[x]) continue;v[x]1;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(f[num][x]a[i].wf[num][y]){f[num][y]f[num][x]a[i].w;if(!v[y]) q.push((node){y,f[num][y]});}}}
}
int main()
{scanf(%lld%lld%lld,n,m,k);p[cnt]1;for(ll i1;im;i){ll x,y,w;scanf(%lld%lld%lld,x,y,w);if(ik)p[cnt]x,p[cnt]y;addl(x,y,w);addl(y,x,w);}memset(f,127,sizeof(f));memset(g,127,sizeof(g));for(ll i1;icnt;i)dij(i,p[i]);MS1k;g[0][1]0;for(ll i0;iMS;i)for(ll j1;jk;j){if(i(1j-1)) continue;ll zi|(1j-1);for(ll ij1;ijcnt;ij)g[z][j*2]min(g[z][j*2],g[i][ij]f[ij][p[j*21]]a[2*j].w),g[z][j*21]min(g[z][j*21],g[i][ij]f[ij][p[j*2]]a[2*j].w);}for(ll i1;icnt;i)ansmin(ans,g[MS-1][i]f[i][1]);printf(%lld,ans);
}
