# 题目

image-20210318200457249

# 题意

给定 t 个点,r 条道路,p 条航线,和一个起点,道路可互相到达,航线只能单向到达,且航线的权值可能为负数,问从起点到各个点的最小距离是多少?若不可到达输出 “NO PATH”

# 思路

把所有道路相连的点组成联通块,给他们编上号,从起点所在的联通块往后跑一个拓扑排序,连通块内跑 dijstla,松弛时发现松驰的点和当前点不在一个连通块内,则把更新的点所在的联通块入度 - 1,大致思路是这样,但是还是有许多细节问题

  1. 为什么一开始要加入入度为 0 的点?
    • 因为要保证拓扑序列的进行。假设 s 所在块编号为 a,a 连向块 c,块 b 连向块 c,且块 a 块 b 不相连。此时,如果你不加入入度为 0 的点,那么 b 块就不会访问到,c 的入度也就不会减到 0,也就不会访问到。
  2. 判断无解为什么不写出 ==inf?
    • 因为有坑 1 的存在。还是上面那个例子,再加 2 个条件:
      1. 块 d-> 块 b,块 a 与块 d 不相连。
      2. d 到 b 的路为负边权
        • 此时显然应该块 b、d 里所有的点都是 NOPATH,而且 dis 都为 inf。但其实在用块 d 内的点更新块 b 时,会松弛成功,因为存在负边权。所以无解时不一定 dis 就为 inf
  3. 对每一个连通块跑最短路时,不知道那个点作为起点,理论上是最小的那个点,但是考虑到可能从一个联通块到当前联通块距离比较小,但是从起点所在的联通块到当前联通块距离较大,但是两条路不相交,即不可互相到达,这样会导致起点到这个联通块的路径反而消失了,所以把所有点放到优先队列里才是合适的做法

# CODE

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int MAXN=500000;
const int INF=0x3f3f3f3f;
struct node{
	int to,next,w;
}e[MAXN];
struct Node{
	int u,d;
	bool operator<(const Node &o)const{
		return d>o.d;
	}
};
int head[MAXN],dis[MAXN],id[MAXN],in[MAXN];
int n,r,p,s,tot,bcnt;
bool vis[MAXN];
vector<int> ve[MAXN];
queue<int> q;
priority_queue<Node> pq;
void add(int u,int v,int w){
	e[tot]={v,head[u],w};
	head[u]=tot++;
}
void dfs(int x){
	ve[bcnt].push_back(x);
	id[x]=bcnt;
	for(int i=head[x];~i;i=e[i].next){
		if(!id[e[i].to]) dfs(e[i].to);
	}
}
void dij(int s){
	for(auto i:ve[s]) pq.push({i,dis[i]});
	while(!pq.empty()){
		Node now=pq.top();
		pq.pop();
		if(vis[now.u]) continue;
		vis[now.u]=1;
		for(int i=head[now.u];~i;i=e[i].next){
			int v=e[i].to,w=e[i].w;
			if(dis[v]>dis[now.u]+w){
				dis[v]=dis[now.u]+w;
				if(id[v]==id[now.u]) pq.push({v,dis[v]});
			}
			if(id[v]!=id[now.u]){
				in[id[v]]--;
				if(in[id[v]]==0) q.push(id[v]);
			}
		}
	}
}
void tupo(){
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	q.push(id[s]);
	for(int i=1;i<=bcnt;i++){
		if(!in[i]) q.push(i);
	}
	while(!q.empty()){
		int fr=q.front();
		q.pop();
		dij(fr);
	}
}
int main()
{
	ios;
	memset(head,-1,sizeof head);
	cin>>n>>r>>p>>s;
	while(r--){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	for(int i=1;i<=n;i++){
		if(!id[i]){
			bcnt++;
			dfs(i);
		}
	}
	while(p--){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		in[id[v]]++;
	}
	tupo();
	for(int i=1;i<=n;i++){
		if(dis[i]>INF/2) cout<<"NO PATH"<<'\n';  // 可能存在到不了的点却被负权边更新了
		else cout<<dis[i]<<'\n';
	}
	return 0;
}
更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝