[Acwing] 342. 道路与航线

前言

t a g : tag : tag: 拓扑 堆优化DIJ 思维 传送门 :

题意 :

给定多个双向边和多个单向边,双向边边权必然为正,单向边可能为负,每个双向边构成的连通块只能由单向边相连,询问从 S S S开始到其他点的最短路

思路 :

首先题意很明显的想让我们分块处理,即先处理出双向边的所有连通块,这样子整个图,就会变成一个 D A G DAG DAG

下面这里就有一条需要注意的是 : D A G DAG DAG上 我们可以线性的时间求出单源最短路

因此我们直接对 D A G DAG DAG求一个最短路即可

code :

// Problem: 道路与航线
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/344/
// Memory Limit: 64 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// Problem: B. Rising Sand
// Contest: Codeforces - Codeforces Round #803 (Div. 2)
// URL: https://codeforces.com/contest/1698/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
typedef pair pii;
#define Fup(i,a,b) for(int i=a;i=b;i--)
#define cer(a) cerr>c;
		road[a].pb({b,c});
		road[b].pb({a,c});
	}
	
	Fup(i,1,t){
		if(!id[i]){
			++bcnt;
			dfs(i);
		}
	}
	
	Fup(i,1,p){
		int a,b,c;cin>>a>>b>>c;
		road[a].pb({b,c});
		deg[id[b]]++;
	}
	
	topsort();
	
	
	Fup(i,1,t){
		if(dist[i] > INF/2)cout