当前位置:网站首页>Roads and routes -- dfs+topsort+dijkstra+ mapping
Roads and routes -- dfs+topsort+dijkstra+ mapping
2022-07-05 01:07:00 【Wawa source】
Algorithm flow
1. Enter all two-way roads first , then DFS
Out all connected blocks , Calculate two arrays :id[]
Store which connected block each point belongs to ;vector<int> block[]
Store the points in each connected block :
2. Enter all routes , At the same time, the penetration of each connected block is counted .
3. Process each connected block in topological order , First, set all entries to 0
The number of the connected block of is added to the queue
in .
4. Take out the number of one connected block from the head of the team at a time bid
5. Will be block[bid]
All points in are added to the heap , Then run for all points in the heap dijkstra
Algorithm .
6. Take out the smallest point in the heap every time ver
.
7. Then traverse ver
All the neighbors of j
. If id[ver]==id[]
, So if j Can be updated , Will j
Insert into the heap : If id[ver]!= id[j]
, Will id[j]
The penetration of this connected block decreases 1
, If reduced 0
了 , Then insert it into the queue of topology sorting
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 25010,M=150010,INF=0x3f3f3f3f;
typedef pair<int, int> PII;
#define x first
#define y second
int e[M],h[N],ne[M],w[M],idx=0;
int n,mr,mp,s;
int bcnt;
vector<int>block[N];
int id[N];
int din[N];
int dist[N];
bool st[N];
queue<int>q;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u,int bid)
{
id[u]=bid,block[bid].push_back(u);
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(!id[j])
dfs(j,bid);
}
}
void dij(int bid)
{
priority_queue<PII,vector<PII>,greater<PII> >heap;
for(auto u:block[bid])
heap.push({
dist[u],u});
while(heap.size())
{
auto t=heap.top();
heap.pop();
int ver=t.y,distance=t.x;
if(st[ver])continue;
st[ver]=true;
for(int i=h[ver];i!=-1;i=ne[i])
{
int j=e[i];
if(id[j]!=id[ver]&&--din[id[j]]==0)q.push(id[j]);
if(dist[j]>dist[ver]+w[i]){
dist[j]=dist[ver]+w[i];
if(id[j]==id[ver])heap.push({
dist[j],j});
}
}
}
}
void topsort()
{
memset(dist,0x3f,sizeof dist);
dist[s]=0;
for(int i=1;i<=bcnt;i++)
if(!din[i])
q.push(i);
while(q.size())
{
int t=q.front();
q.pop();
dij(t);
}
}
signed main()
{
memset(h, -1, sizeof h);
cin>>n>>mr>>mp>>s;
for(int i=1;i<=mr;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
for(int i=1;i<=n;i++)
if(!id[i])
{
bcnt++;
dfs(i,bcnt);
}
for(int i=1;i<=mp;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
din[id[b]]++;
}
topsort();
for(int i=1;i<=n;i++)
if(dist[i]>INF/2)cout<<"NO PATH"<<endl;
else cout<<dist[i]<<endl;
return 0;
}
边栏推荐
- 全栈开发提效神器——ApiFox(Postman + Swagger + Mock + JMeter)
- 如果消费互联网比喻成「湖泊」的话,产业互联网则是广阔的「海洋」
- Basic operation of database and table ----- the concept of index
- Database postragesql client connection default
- 华为百万聘请数据治理专家!背后的千亿市场值得关注
- Parameter passing mechanism of member methods
- 测试部新来了个00后卷王,上了年纪的我真的干不过了,已经...
- 创新引领方向 华为智慧生活全场景新品齐发
- 【大型电商项目开发】性能压测-性能监控-堆内存与垃圾回收-39
- [flutter topic] 64 illustration basic textfield text input box (I) # yyds dry goods inventory #
猜你喜欢
Behind the cluster listing, to what extent is the Chinese restaurant chain "rolled"?
Senior Test / development programmers write no bugs? Qualifications (shackles) don't be afraid of mistakes
Pandora IOT development board learning (RT thread) - Experiment 4 buzzer + motor experiment [key external interrupt] (learning notes)
Single step debugging of master data reading of SAP commerce cloud products
[development of large e-commerce projects] performance pressure test - Performance Monitoring - heap memory and garbage collection -39
Pycharm professional download and installation tutorial
各大主流编程语言性能PK,结果出乎意料
[wave modeling 3] three dimensional random real wave modeling and wave generator modeling matlab simulation
POAP:NFT的采用入口?
dotnet-exec 0.6.0 released
随机推荐
有哪些收益稳定的理财产品,这两个都不错
Single step debugging of master data reading of SAP commerce cloud products
[development of large e-commerce projects] performance pressure test - Optimization - impact of middleware on performance -40
Pandora IOT development board learning (RT thread) - Experiment 4 buzzer + motor experiment [key external interrupt] (learning notes)
“薪資倒掛”、“畢業生平替” 這些現象說明測試行業已經...
Daily practice (18): stack containing min function
Hand drawn video website
Insert sort of sort
Sorting selection sorting
当产业互联网时代真正发展完善之后,将会在每一个场景见证巨头的诞生
Chia Tai International Futures: what is the master account and how to open it?
Implementation steps of master detail detail layout mode of SAP ui5 application
Basic operation of database and table ----- phased test II
Relationship between classes and objects
各大主流编程语言性能PK,结果出乎意料
Delaying wages to force people to leave, and the layoffs of small Internet companies are a little too much!
小程序直播 + 电商,想做新零售电商就用它吧!
BGP comprehensive experiment
SAP UI5 应用的主-从-从(Master-Detail-Detail)布局模式的实现步骤
Expose testing outsourcing companies. You may have heard such a voice about outsourcing