洛谷 [P3008] 道路与航线

最短路

因为有负权边,所以不能 dijkstra ,本题数据还卡 SPFA

但是我们发现,有负权的都是有向边,而且如果把无向边连成的联通块看成一个点的话,有向边就连成了一个 DAG,所以我们可以对所有的联通块用dij求最短路

在 DAG上用拓扑序求最短路

注意:

堆优化的 Dijkstra 在定义的结构体重载运算符的时候注意相反

因为存在负权边,所以两点不可达,不等价于两点间的距离 == inf ,应为两点间的距离大于一个很大的数

#include <iostream>

#include <cmath>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <queue>

#include <vector>

#include <cstring>

using namespace std;

const int MAXN = 100005;

int init() {

	int rv = 0, fh = 1;

	char c = getchar();

	while(c < '0' || c > '9') {

		if(c == '-') fh = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9'){

		rv = (rv<<1) + (rv<<3) + c - '0';

		c = getchar();

	}

	return fh * rv;

}

int head[MAXN], n, m1, m2, s, nume, id[MAXN], tot, dis[MAXN], cnt[MAXN];

bool f[MAXN];

vector <int> ve[25005];

struct edge{

	int to, nxt, dis;

}e[MAXN<<1];

void adde(int from, int to, int dis) {

	e[++nume].to = to;

	e[nume].nxt = head[from];

	e[nume].dis = dis;

	head[from] = nume;

}

void dfs(int u) {

	if(id[u]) return;

	id[u] = tot;

	ve[tot].push_back(u);

	for(int i = head[u]; i; i = e[i].nxt) {

		int v = e[i].to;

		dfs(v);

	}

}

struct node{

	int num, val;

	bool operator < (const node & b) const{

		return val > b.val;

	}

};

priority_queue <node> q;

queue <int> qq;

void dij(int x){

	for(int i = 0; i < (int)ve[x].size(); i++) q.push((node){ve[x][i], dis[ve[x][i]]});

	while(!q.empty()) {

		node u = q.top(); q.pop();

		if(f[u.num]) continue;

		f[u.num] = 1;

		for(int i = head[u.num]; i; i = e[i].nxt) {

			node v;

			v.num = e[i].to;

			if(id[v.num] == id[u.num] && dis[v.num] > dis[u.num] + e[i].dis) {

				dis[v.num] = dis[u.num] + e[i].dis;

				v.val = dis[v.num];

				q.push(v);

			}

			if(id[v.num] != id[u.num]) {

				dis[v.num] = min(dis[v.num], dis[u.num] + e[i].dis);

				cnt[id[v.num]]--;

				if(!cnt[id[v.num]]) {

					qq.push(id[v.num]);

				}

			}

		}

	}

}

int main() {

	n = init(); m1 = init(); m2 = init(); s = init();

	for(int i = 1; i <= m1; i++) {

		int u = init(), v = init(), di = init();

		adde(u, v, di); adde(v, u, di);

	}

	for(int i = 1; i <= n; i++) {if(!id[i]) tot++;dfs(i);}

	for(int i = 1; i <= m2; i++) {

		int u = init(), v = init(), di = init();

		adde(u, v, di);cnt[id[v]]++;

	}

	memset(dis, 0x3f, sizeof(dis));

	dis[s] = 0;

	for(int i = 1; i <= tot; i++) if(!cnt[i]) qq.push(i);

	while(!qq.empty()) {

		int v = qq.front(); qq.pop();

		dij(v);

	}

	for(int i = 1; i <= n; i++) {

		if(dis[i] > 100000000) printf("NO PATH\n");

		else printf("%d\n", dis[i]);

	}

	return 0;

}

巴特西

洛谷 [P3008] 道路与航线

最短路

最新文章

热门文章