当前位置: 首页 > news >正文

企业建设网站有哪些费用谷歌关键词分析工具

企业建设网站有哪些费用,谷歌关键词分析工具,网站设计师岗位职责,泉州网站优化正题 题目链接:https://www.ybtoj.com.cn/contest/114/problem/1 题目大意 给出nnn个点mmm条边的一张无向图#xff0c;对于每个点iii求不经过i∼1i\sim 1i∼1的最短路的第一条边的情况下iii到111的最短路 数据保证这条边唯一 n∈[1,105],m∈[1,2105],c∈[1,103]n\in[1,10^…正题 题目链接:https://www.ybtoj.com.cn/contest/114/problem/1 题目大意 给出nnn个点mmm条边的一张无向图对于每个点iii求不经过i∼1i\sim 1i∼1的最短路的第一条边的情况下iii到111的最短路 数据保证这条边唯一 n∈[1,105],m∈[1,2×105],c∈[1,103]n\in[1,10^5],m\in[1,2\times 10^5],c\in[1,10^3]n∈[1,105],m∈[1,2×105],c∈[1,103] 解题思路 因为保证的那个东西所以图的最短路树真的是一棵树了所以先跑出最短路树考虑在最短路树上面搞。 然后题目限制了我们不能从树上的祖先那条边过来这样就分为了两种情况。一种是从该点的子树外面连过来的边另一种是从子树中走上来的边。第二种很麻烦因为子树的最短路是用该节点的最短路扩展的所以不能直接使用。 考虑一条非树边(x,y)(x,y)(x,y)这条边会扩展一条disywdis_ywdisy​w到xxx的路径。disxdis_xdisx​表示1∼x1\sim x1∼x的最短路。 并且这条边可以使用到LCA(x,y)LCA(x,y)LCA(x,y)处此时xxx的祖先们都不包含yyy在子树内可以直接用yyy的子树扩展。 所以可以维护一个左偏树每次合并两个儿子的信息如果堆顶的边需要被删除就删除。需要写一个lazylazylazy标记来修改整棵树 时间复杂度O(nlog⁡n)O(n\log n)O(nlogn) code #includecstdio #includecstring #includealgorithm #includequeue #includevector #define mp(x,y) make_pair(x,y) using namespace std; const int N4e510; struct point{int val,x,y;point(int v0,int xx0,int yy0){valv;xxx;yyy;return;} }; bool operator(point x,point y) {return x.valy.val;} struct Heap{point val[N];int t[N][2],lazy[N],dis[N];void Downdata(int x){if(!lazy[x])return;int lst[x][0],rst[x][1];lazy[ls]lazy[x];lazy[rs]lazy[x];val[ls].vallazy[x];val[rs].vallazy[x];lazy[x]0;return;}int Merge(int x,int y){Downdata(x);Downdata(y);if(!x||!y)return xy;if(val[y]val[x])swap(x,y);int lst[x][0],rst[x][1];rsMerge(rs,y);if(dis[rs]dis[ls])swap(ls,rs);dis[x]dis[rs]1;return x;}int Del(int x){int lst[x][0],rst[x][1];val[x]0;return Merge(ls,rs);} }T; struct node{int to,next,w; }a[N]; int n,m,tot,cnt,num,ls[N],f[N]; int rfn[N],p[N],ans[N]; bool v[N];vectorint G[N]; priority_queuepairint,int q; void addl(int x,int y,int w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;return; } void dij(){memset(f,0x3f,sizeof(f));q.push(mp(0,1));f[1]0;while(!q.empty()){int xq.top().second;q.pop();if(v[x])continue;v[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(f[x]a[i].wf[y]){f[y]f[x]a[i].w;q.push(mp(-f[y],y));}}}return; } void dfs(int x){rfn[x]cnt;for(int i0;iG[x].size();i){int yG[x][i];dfs(y);T.val[p[y]].valf[y]-f[x];T.lazy[p[y]]f[y]-f[x];p[x]T.Merge(p[x],p[y]);}for(int ils[x];i;ia[i].next){int ya[i].to;if(f[x]a[i].wf[y])continue;if(f[y]a[i].wf[x])continue;T.val[num]point(f[y]a[i].w,x,y);p[x]T.Merge(p[x],num);}while(1){if(!p[x]){ans[x]-1;break;}point wT.val[p[x]];if(rfn[w.y]rfn[x]){p[x]T.Del(p[x]);continue;}ans[x]w.val;break;}return; } int main() {freopen(pal.in,r,stdin);freopen(pal.out,w,stdout);scanf(%d%d,n,m);for(int i1;im;i){int x,y,w;scanf(%d%d%d,x,y,w);addl(x,y,w);addl(y,x,w);}dij();for(int x1;xn;x)for(int ils[x];i;ia[i].next){int ya[i].to;if(f[x]a[i].wf[y])G[x].push_back(y);}dfs(1);for(int i2;in;i)if(!ans[i])puts(-1);else printf(%d\n,ans[i]);return 0; }
http://wiki.neutronadmin.com/news/341455/

相关文章:

  • 网站运营面试wordpress星座主题自适应
  • 企业网站ui设计网站建设计划图
  • 有经验的常州网站建设网页美工设计的要点包括
  • 整站seo优化推广ps软件下载电脑版免费破解版
  • 南通优化网站扬州建设网站公司
  • 哪个着陆页网站做水果网站特点分析报告
  • 小城镇建设网站参考文献wordpress网址访问慢
  • wordpress 导航网站模板下载wordpress前台修改用户头像
  • 网站源码下载有什么用东莞手机app开发
  • 微网站设计尺寸北住房和城乡建设厅网站
  • seo网站查询中国核工业二三建设有限公司招聘
  • WordPress电影公司网站主题在淘宝上开网店的详细步骤
  • seo整站优化网站建设株洲网站搜索优化
  • 郑州哪家做网站最好中装建设法人
  • 成华区统一建设办公室网站从化低价网站建设
  • 张家港手机网站设计网站图片一般多大尺寸
  • 最早做美食团购的网站深圳网站设计+建设首选深圳市
  • 茶文化网站开发中关村在线手机报价
  • 昆明网站优化中咨城建设计有限公司官方网站
  • 网站设计合同附件南通seo网站优化软件
  • 企业建站公司可以免费发外链的论坛
  • 统计局网站集约化建设方案官方网页qq登陆
  • 孝感市网站建设wordpress 百度联盟
  • asp.net网站访问统计专业建设思路与措施
  • 关于做数学 平方差公式的网站橙米网站建设
  • iis网站下载海宁市建设局官方网站
  • 电脑学校培训夺宝网站怎样做优化
  • 网站的二级网页关键词跨境经验分享
  • wordpress 列表分页深圳百度网站排名优化
  • 安徽省建设干部学校网站怎样建设档案馆网站