题目描述
农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到 T T T 个城镇,编号为 1 ∼ T 1\sim T 1∼T。
这些城镇之间通过 R R R 条道路 (编号为 1 1 1 到 R R R) 和 P P P 条航线 (编号为 1 1 1 到 P P P) 连接。
每条道路 i i i 或者航线 i i i 连接城镇 A i A_i Ai 到 B i B_i Bi,花费为 C i C_i Ci。
对于道路, 0 ≤ C i ≤ 10 , 000 0≤C_i≤10,000 0≤Ci≤10,000;然而航线的花费很神奇,花费 C i C_i Ci 可能是负数( − 10 , 000 ≤ C i ≤ 10 , 000 −10,000≤C_i≤10,000 −10,000≤Ci≤10,000)。
道路是双向的,可以从 A i A_i Ai 到 B i B_i Bi,也可以从 B i B_i Bi 到 A i A_i Ai,花费都是 C i C_i Ci。
然而航线与之不同,只可以从 A i A_i Ai 到 B i B_i Bi。
事实上,由于最近恐怖主义太嚣张,为了社会和谐,出台了一些政策:保证如果有一条航线可以从 A i A_i Ai 到 B i B_i Bi,那么保证不可能通过一些道路和航线从 B i B_i Bi 回到 A i A_i Ai。
由于约翰的奶牛世界公认十分给力,他需要运送奶牛到每一个城镇。
他想找到从发送中心城镇 S S S 把奶牛送到每个城镇的最便宜的方案。
输入格式
第一行包含四个整数 T , R , P , S T,R,P,S T,R,P,S。
接下来 R R R 行,每行包含三个整数(表示一个道路) A i , B i , C i A_i,B_i,C_i Ai,Bi,Ci。
接下来 P P P 行,每行包含三个整数(表示一条航线) A i , B i , C i A_i,B_i,C_i Ai,Bi,Ci。
输出格式
第
1..
T
1..T
1..T 行:第
i
i
i 行输出从
S
S
S 到达城镇
i
i
i 的最小花费,如果不存在,则输出 NO PATH
。
样例 #1
样例输入 #1
6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10
样例输出 #1
NO PATH
NO PATH
5
0
-95
-100
提示
【数据范围】
1
≤
T
≤
25000
1≤T≤25000
1≤T≤25000,
1
≤
R
,
P
≤
50000
1≤R,P≤50000
1≤R,P≤50000,
1
≤
A
i
,
B
i
,
S
≤
T
1≤A_i,B_i,S≤T
1≤Ai,Bi,S≤T
算法思想
根据题目描述:
- 道路是双向的,可以从A到B,也可以从B到A,花费都是C;而航线是单向的,只可以从A到B
- 题目中保证如果有一条航线可以从A到B,那么保证不可能通过一些道路和航线从B回到A
- 题目要求的就是起点到各个点的最短距离之和
显然是求单源最短路问题,但图中带有负权边,不能直接使用Dijkstra算法。考虑题目中给出的性质,双向边都是非负的,只有单向边可能是负的,并且单向边不构成环。
如果只把双向边添加到图中,那么会形成若干个连通块,可以把每个连通块看作一个点,再把单向边添加到图中,会得到一张有向无环图。在有向无环图中,无论边权正负,都可以按照拓扑序进行遍历,在线性时间复杂度内求出单源最短路。
算法流程
- 只把双向边加入图中,用深度优先遍历划分图中的连通块,记 c [ u ] c[u] c[u]为节点 u u u所属连通块的编号。
- 统计每个连通块的总入度,即 d [ i ] d[i] d[i]为第 i i i个连通块的总入度
- 建立一个队列,存储连通块的编号,用于拓扑排序。最初队列中包含所有入度为 0 0 0的连通块编号。设 d i s [ S ] = 0 dis[S]=0 dis[S]=0表示起点到自己的距离为0,其余点的初始化为无穷大。
- 取出队头的连通块
i
i
i,对该连通块执行堆优化的Dijkstra算法,重复该步骤直至队列为空:
- 建立一个堆,把第 i i i个连通块中所有节点加入堆中
- 从堆中取出 d i s [ u ] dis[u] dis[u]最小的节点 u u u
- 若 u u u被扩展过,则回到步骤 2 2 2
- 遍历从 u u u出发的所有边 ( u , v , w ) (u, v, w) (u,v,w),用 d i s [ u ] + w dis[u]+w dis[u]+w更新 d i s [ v ] dis[v] dis[v]
- 如果 u u u和 v v v在同一个连通块中,即 c [ u ] = c [ v ] c[u]=c[v] c[u]=c[v],并且 d i s [ v ] dis[v] dis[v]被更新,则将 v v v插入堆中
- 若 c [ u ] ≠ c [ v ] c[u]\ne c[v] c[u]=c[v],则令 d [ c [ v ] ] d[c[v]] d[c[v]]减去 1 1 1,如果减到 0 0 0,则将 c [ v ] c[v] c[v]插入拓扑排序的队列尾部。
- 重复 2 ∼ 6 2\sim6 2∼6,直至堆为空
时间复杂度
整个算法的时间复杂度为 O ( T + P + R l o g T ) O(T+P+RlogT) O(T+P+RlogT)
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 25010, INF = 0x3f3f3f3f;
struct Edge
{
int v, w;
};
vector<Edge> g[N];
int T, R, P, S, c[N], cnt, d[N], dis[N], st[N];
vector<int> b[N]; //存储每个连通块中的点
queue<int> q;
void dfs(int u, int k) //将与u连通的点加入第k个连通块
{
c[u] = k; b[k].push_back(u); //将u加入k的连通块集合中
for(Edge u : g[u])
{
int v = u.v;
if(!c[v]) dfs(v, k);
}
}
void dijkstra(int k)
{
priority_queue<PII, vector<PII>, greater<PII>> h;
//将连通块中所有点加入队列
for(int u : b[k])
h.push({dis[u], u});
while(h.size())
{
PII t = h.top(); h.pop();
int u = t.second;
if(st[u]) continue;
st[u] = 1;
for(Edge e : g[u])
{
int v = e.v, w = e.w;
//如果不在同一个连通块
if(c[u] != c[v] && -- d[c[v]] == 0) q.push(c[v]);
if(dis[v] > dis[u] + w) //能够缩短到v点的距离
{
dis[v] = dis[u] + w;
if(c[u] == c[v]) //注意,如果u和v在同一个连通块,才加入堆中继续求最短距离
h.push({dis[v], v});
}
}
}
}
void topsort()
{
memset(dis, 0x3f, sizeof dis);
dis[S] = 0;
for(int i = 1; i <= cnt; i ++) //将入度为0的连通块加入拓扑排序的队列中
{
if(!d[i]) q.push(i);
}
while(q.size())
{
int k = q.front(); q.pop();
dijkstra(k); //求连通块中的最短路
}
}
int main()
{
scanf("%d%d%d%d", &T, &R, &P, &S);
for(int i = 1; i <= R; i ++)
{
int u, v, w;
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(!c[i]) dfs(i, ++ cnt); //注意连通块的编号应从1开始
for(int i = 1; i <= P; i ++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].push_back({v, w});
d[c[v]] ++; //v所在的连通块的入度增加1
}
topsort(); //拓扑排序,按照拓扑序计算最短路
for(int i = 1; i <= T; i ++)
if(dis[i] > INF / 2) puts("NO PATH");
else printf("%d\n", dis[i]);
}