「题解」Roads and Planes

题目链接

Luogu P3008 [USACO11JAN]Roads and Planes G

分析

直接 SPFA 根据数据范围是会超时的，但由于这是一道老题，所以优先队列优化 SPFA 也是可以通过的，但这并不是正解，下文不加以介绍。

根据题意，负边权仅存在于有向边，所以可以把所有无向边的连通块处理出来，块内采用堆优化 dijkstra，块与块之间用拓扑排序。

具体如下：

1. 读入无向边，DFS 求出连通块，同时记录每个连通块有哪些点，用于 dijkstra
2. 读入有向边，记录每个连通块的入度（拓扑排序用）
3. 拓扑排序，寻找入度为 $0$ 的点入队，每次取队首进行 dijkstra：
   1. 将这个联通块内所有点插入堆中
   2. 取出堆顶元素 $x$，遍历可到达的点 $y$，更新 dis：
      • 如果 $x$ 和 $y$ 在同一连通块内，插入堆
      • 否则，将 $y$ 所在的连通块的入度减一。检查 $y$ 所在的连通块入度是否为 $0$，如果为 $0$ 则入队。

参考代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>

using namespace std;

const int N = 25010, M = 50010;

struct edge{
	int to;
	int dis;
};

int t, r, p, s;
int u, v, w;
int col[N], cnt;
int dis[N];
int fv[N];
int rd[N];
vector <int> kuai[N];
vector <edge> g[N];

void dfs(int x){
	col[x] = cnt;
	kuai[cnt].push_back(x);
	for(auto i : g[x]){
		if(!col[i.to]){
			dfs(i.to);
		}
	}
}

pair <int, int> tp;

priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > dq;

queue <int> tq;

void dij(int x){
	
	for(auto i : kuai[x]){
		dq.push(make_pair(dis[i], i));
	}
	
	while(!dq.empty()){
		tp = dq.top();
		dq.pop();
		
		if(fv[tp.second]){
			continue;
		}
		
		fv[tp.second] = 1;
		
		for(auto i : g[tp.second]){
			
			if(tp.first + i.dis < dis[i.to]){
				dis[i.to] = tp.first + i.dis;
				if(col[tp.second] == col[i.to]){
					dq.push(make_pair(dis[i.to], i.to));
				}
			}
			
			rd[col[i.to]]--;
			if(col[tp.second] != col[i.to] && rd[col[i.to]] == 0){
				tq.push(col[i.to]);
			}
		}
		
	}
	
}

void topo(){
	
	for(int i = 1; i <= cnt; i++){
		if(rd[i] == 0){
			tq.push(i);
		}
	}
	
	while(!tq.empty()){
		int tmpp = tq.front();
		tq.pop();
		dij(tmpp);
	}
	
}

int main(){
	
	scanf("%d%d%d%d", &t, &r, &p, &s);
	
	while(r--){
		scanf("%d%d%d", &u, &v, &w);
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	
	for(int i = 1; i <= t; i++){
		if(!col[i]){
			cnt++;
			dfs(i);
		}
	}
	
	while(p--){
		scanf("%d%d%d", &u, &v, &w);
		g[u].push_back({v, w});
		rd[col[v]]++;
	}
	
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	
	topo();
	
	for(int i = 1; i <= t; i++){
		if(dis[i] > 1e9){
			puts("NO PATH");
		}else{
			printf("%d\n", dis[i]);
		}
	}
	
	return 0;
}