Acwing 342：道路与航线（含有无环负权边的最短路问题 dijkstra+topsort）题解

迈不过友情╰ 2022-11-18 13:58 156阅读 0赞

### 题目大意 ###

原题链接：[Acwing 342：道路与航线][Acwing 342]

各城市之间有道路也有航线，道路是双向的且权值为正，航线是单向的且权值有负，保证航线连接的两个城市ab，只能从a到b，而不能以任何途径从b到a，路的权值是花费。  
给定一个起点，求从起点到其余所有城市的最小花费。

### 思路 ###

根据题意，所有道路相连的城市都是一个连通的无向图，将这样的城市群看作一个团，整张图会有很多个团，每个团之间有单向的边，权值可能是负数，如下图，黑边是道路，红边是航线：  
![eg][]  
既有正边又有负边的单源最短路问题应该怎么做？dij不能处理负权边，因此肯定首先会想到spfa，但spfa已死 ，很容易被一个菊花图卡掉，这道题就被卡掉了。所以我们就要看这个图的性质。每个团内部可以用[堆优化的dijstra][dijstra]来求最短路，而每个团之间一定无环（题意，没有任何途径从航线终点到航线起点），那么将每个团做一个[拓扑排序][Link 1]，然后线性的扫描一遍，就可以处理团之间的边了。我们用id数组存每个点所属的团的编号，block的vector数组来存每个团内有哪些点。  
然后**按照拓扑序对每个团内的点做一遍堆优化的dij**，**边拓扑排序边做dij**：当团内dij时若访问到团外的点，就将点所在的团的入度减一（topsort），然后正常更新dis数组即可。（具体步骤可以看代码详解）

这样子就**灵活的处理掉了dij不能处理负权边的问题**，因为所有团是按拓扑序排的，所以线性的扫一遍求最短路是没问题的。而每个团做dij时，将当前点走到的点记为v，若v是团内的点就正常更新dis，判断入堆即可；若v是团外的点，则该边可能是负数，我们就直接更新dis\[v\]即可，然后将v所在团的入度减一，若入度为0，将v所在的团加入拓扑序列。然后我们判断若dis\[i\] > INF/2，就说明没有路到i点，因为若i的团在起点的团的拓扑序的前面，且i之前有团用负边更新到了i点，因此i点的距离可能比INF小一点，所以只需用一个较大的数来判断，我们取INF/2来判断，若大于他，都说明没有路，输出NO PATH，其余输出dis\[i\]即可。

### 代码详解 ###

#include<iostream>
    #include<cstring>
    #include<queue>
    #include<vector>
    #define x first
    #define y second
    using namespace std;
    typedef pair<int,int> PII;
    const int N = 25010,M = 150010,INF = 0x3f3f3f3f;
    
    int n,r,p,s;
    int e[M],ne[M],w[M],h[N],idx;	//链式前向星建图
    int id[N],dis[N],d[N],bcnt;		//id是每个点所属的连通块编号，dis是到各点的距离，d是入度，bcnt是连通块编号
    bool vis[N];	//dij所需的bool数组
    vector<int> block[N];	//block[i]存编号为i的连通块中的所有点
    queue<int> q;	//topsort的队列
    
    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)		//dfs划分连通块
    { 
    	id[u] = bid;		//u点的连通块编号是bid
    	block[bid].push_back(u);	//bid号连通块内加入u点
    
    	for(int i = h[u];~i;i = ne[i])	//循环下一个点
    	{ 
    		int v = e[i];
    		if(!id[v])	//如果能走到该点且没被访问过
    			dfs(v,bid);	//就搜他
    	}
    }
    
    void dijkstra(int bid)
    { 	
    	priority_queue<PII,vector<PII>,greater<PII> > heap;	//建堆优化
    	for(auto u : block[bid])		//将该连通块中的所有点加入堆中（这里要将所有点都加入，因为dij算法的原理）
    		heap.push({ dis[u],u});
    	while(heap.size())	//dij算法模板
    	{ 
    		int u = heap.top().y;
    		heap.pop();
    		if(vis[u])
    			continue;
    		vis[u] = 1;
    		for(int i = h[u];~i;i = ne[i])
    		{ 
    			int v = e[i];
    			if(id[v] != id[u])		//如果搜到的下一个点不是该连通块内的，那么就给下一个连通块的入度-1
    			{ 
    				d[id[v]]--;
    				if(d[id[v]] == 0)	//如果入度为0加入队列
    					q.push(id[v]);
    			}
    			if(dis[v] > dis[u] + w[i])
    			{ 
    				dis[v] = dis[u] + w[i];
    				if(id[v] == id[u])	//如果更新了且搜到的点和当前点是同一个连通块，就加入堆中
    					heap.push({ dis[v],v});
    			}
    		}
    	}
    }
    
    void topsort()
    { 
    	memset(dis,INF,sizeof dis);		//先初始化dis数组
    	dis[s] = 0;
    	for(int i = 1;i <= bcnt;i++)
    		if(d[i] == 0)		//所有连通块中入度为0的加入队列
    			q.push(i);
    	while(q.size())	
    	{ 
    		int cur = q.front();
    		q.pop();
    		dijkstra(cur);		//每次取队列第一个连通块跑dij
    	}
    }
    
    int main()
    { 
    	cin >> n >> r >> p >> s;	//n是总点数，r是道路数，p是航线数，s是起点
    	memset(h,-1,sizeof h);
    	while(r--)
    	{ 
    		int a,b,c;
    		cin >> a >> b >> c;
    		add(a,b,c);		//道路建双向边
    		add(b,a,c);
    	}
    	for(int i = 1;i <= n;i++)	//dfs给每个连通块标号，id是每个点所在的连通块的编号
    		if(!id[i])		//如果一个点没访问过，就dfs他
    			dfs(i,++bcnt);
    	while(p--)
    	{ 
    		int a,b,c;
    		cin >> a >> b >> c;
    		add(a,b,c);		//航线建单向边
    		d[id[b]]++;		//b点所在的连通块的入度++
    	}
    	topsort();		//对每个连通块拓扑排序
    	for(int i = 1;i <= n;i++)
    	{ 
    		if(dis[i] > INF/2)	//如果dis[i] > INF/2就算无路
    			cout << "NO PATH" << endl;
    		else
    			cout << dis[i] << endl;
    	}
    
    	return 0;
    }

[Acwing 342]: https://www.acwing.com/problem/content/344/
[eg]: /images/20221022/3d25bdce5ef140f39ea9fce0a0a057a1.png
[dijstra]: https://blog.csdn.net/qq_45735851/article/details/106564326
[Link 1]: https://blog.csdn.net/qq_45735851/article/details/106251880