2020-2021:teams:namespace:2020洛谷多校day1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:namespace:2020洛谷多校day1 [2020/05/11 21:12] great_designer [样例] |
2020-2021:teams:namespace:2020洛谷多校day1 [2020/05/18 18:07] (当前版本) great_designer |
||
|---|---|---|---|
| 行 394: | 行 394: | ||
| ====题解==== | ====题解==== | ||
| - | 原题题解如下： | + | 我一开始直觉是统计圈的个数（破圈），但后来发现当同时到达顶点的时候，只统计一次爆炸而不是多次，最后只好打算模拟bfs…… |
| - | 在点上爆炸意味着存在至少两个点可以是他最短路上的前驱；在边上爆炸意味着这条边不在最短路里。因此求出最短路即可。 | + | 题解放进了这个页面：[[广度优先搜索_bfs_与标数最短路_dijkstra]] |
| - | + | ||
| - | 边权≤ 9 并不意味着可以使用SPFA。本题的本意是使用O(nw) 的桶排序Dijkstra, 但是由于vector实现的桶排Dijkstra 和邻接表+ priority_queue 实现的O(mlogm) Dijkstra 速度在使用输入随机数生成器的方法开大数据后没法拉开差距，因此为了避免卡常数都放了过去。 | + | |
| - | + | ||
| - | 本题真的不卡常数，测出来时限不宽是因为读入太慢了。 | + | |
| - | + | ||
| - | （以上） | + | |
| - | + | ||
| - | 总之大概的意思是，这东西恰好是最短图标记图后直接算出来。 | + | |
| - | + | ||
| - | 我们总共有三门课讲到最短路：数据结构、离散II、算法。大概就是把BFS里面的queue换成priority_queue就行了。也就是说，如果所有的边权都为1，priority_queue也可以用queue替代。 | + | |
| - | + | ||
| - | （推荐任韩图论，一本跨越了数竞和计竞的高中数竞书） | + | |
| - | + | ||
| - | <del>然而就是没想到这层。我一开始直觉是统计圈的个数（破圈），但后来发现当同时到达顶点的时候，只统计一次爆炸而不是多次，最后只好打算模拟bfs……</del> | + | |
| - | + | ||
| - | 去年的水专栏：[[https://www.bilibili.com/read/cv4136755|Dijkstra的板子分析]] | + | |
| - | + | ||
| - | <code C++> | + | |
| - | + | ||
| - | #include<stdio.h> | + | |
| - | #include<string.h> | + | |
| - | #include<queue> | + | |
| - | + | ||
| - | using namespace std; | + | |
| - | + | ||
| - | struct node | + | |
| - | { | + | |
| - | int to,next,val; | + | |
| - | }; | + | |
| - | + | ||
| - | struct node e[10000050]; | + | |
| - | + | ||
| - | int head[1000005],cnt,n,m,K; | + | |
| - | + | ||
| - | void add(int first,int second,int z) | + | |
| - | { | + | |
| - | e[cnt]=(struct node){second,head[first],z}; | + | |
| - | head[first]=cnt++; | + | |
| - | } | + | |
| - | + | ||
| - | priority_queue<pair<int,int> > q; | + | |
| - | + | ||
| - | int dis[1000005],vis[1000005],ans,used[1000005]; | + | |
| - | + | ||
| - | void Dijkstra() | + | |
| - | { | + | |
| - | q.push(make_pair(0,1)); | + | |
| - | memset(dis,0x3f,sizeof(dis)); | + | |
| - | dis[1]=0; | + | |
| - | while(!q.empty()) | + | |
| - | { | + | |
| - | int first = q.top().second; | + | |
| - | q.pop(); | + | |
| - | if(vis[first]) | + | |
| - | { | + | |
| - | continue; | + | |
| - | } | + | |
| - | vis[first] = 1; | + | |
| - | int i; | + | |
| - | for(i=head[first];i!=-1;i=e[i].next) | + | |
| - | { | + | |
| - | int to1 = e[i].to; | + | |
| - | if(dis[to1]>dis[first]+e[i].val) | + | |
| - | { | + | |
| - | dis[to1]=dis[first]+e[i].val; | + | |
| - | used[to1]=1; | + | |
| - | q.push(make_pair(-dis[to1],to1)); | + | |
| - | } | + | |
| - | else if(dis[to1]==dis[first]+e[i].val) | + | |
| - | { | + | |
| - | used[to1]++; | + | |
| - | } | + | |
| - | } | + | |
| - | } | + | |
| - | } | + | |
| - | + | ||
| - | int main() | + | |
| - | { | + | |
| - | scanf("%d%d",&n,&m); | + | |
| - | memset(head,-1,sizeof(head)); | + | |
| - | int i,x,y,z; | + | |
| - | for(i=1;i<=m;i++) | + | |
| - | { | + | |
| - | scanf("%d%d%d",&x,&y,&z); | + | |
| - | add(x,y,z); | + | |
| - | add(y,x,z); | + | |
| - | } | + | |
| - | Dijkstra(); | + | |
| - | for(i=1;i<=n;i++) | + | |
| - | { | + | |
| - | if(used[i]>=2) | + | |
| - | { | + | |
| - | used[i]--; | + | |
| - | } | + | |
| - | m-=used[i]; | + | |
| - | } | + | |
| - | printf("%d\n",m); | + | |
| - | } | + | |
| - | + | ||
| - | </code> | + | |
| =====C===== | =====C===== | ||
| 行 757: | 行 657: | ||
| 我想新开一个页面来讲解本题。题解也先放进去了。 | 我想新开一个页面来讲解本题。题解也先放进去了。 | ||
| - | [[裴蜀定理]] | + | [[裴蜀定理与一次不定方程]] |
2020-2021/teams/namespace/2020洛谷多校day1.1589202764.txt.gz · 最后更改: 2020/05/11 21:12 由 great_designer
