dfs连通块+topsort+dijkstra
道路是双向边,且权值非负,航道单向边且有正有负。如果有一条 航线A->B,那么A~B之间不会有 道路相连,否则会构成环
题意明确,说一下大致过程:
1.判断每个点属于哪个连通块,同一个连通块存到一个集合里,比较巧妙的一点是:先add双向边,此时单向边(航道)并未加入,所以不是一个连通图,可以划分连通块
2.将每个连通块看成一个顶点,那么整张地图就可以堪称一个拓扑图,根据拓扑排序常规做法,将入度为0的点(块)加入队列,遍历其周围的点(块),并使其入度-1(如何让入度-1,看第四条dijkstra内部操作),如果入度为0则继续加入队列中。
3.每个连通块内部是一个无向权值非负图,可以跑dijkstra求最短路,但是除了第一个连通块之外,并不知道其他连通块的起点在哪,我们可以直接将所有点全部加入堆中,由于很多点dist[i]=0x3f3f3f3f,并且由于是小顶堆,所以起点(一个连通块只有一个起点)会被自动放到开头,并不会对结果造成影响。
4.连通块内部dijkstra时,如果遍历到不属于同一个连通块的点时,使其入度-1,距离更新可以算上不是一个连通块的点,但是不能加入堆中,否则会当成一个连通块中的点处理掉。
5.由于权值有正有负,所以判断是否连通不能直接判断是否等于INF,大于max权值即可,这里为了方便直接大于INF/2
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int>PII;
const int N = 25010;
const int M = 5e4 * 3 + 10;
int n, mr, mp, s;
int id[N];
int h[N], e[M], ne[M], w[M], idx;
int dist[N], din[N];
vector<int>block[N];
int bcnt;
bool st[N];
queue<int>q;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int bid)
{
id[u] = bid, block[bid].push_back(u);
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!id[j])dfs(j, bid);
}
}
void dijkstra(int bid)
{
priority_queue<PII, vector<PII>, greater<PII>>heap;
for (auto x : block[bid])heap.push({ dist[x],x });
while (heap.size())
{
auto t = heap.top();
heap.pop();
if (st[t.y])continue;
st[t.y] = true;
for (int i = h[t.y]; ~i; i = ne[i])
{
int j = e[i];
if (id[j] != id[t.y] && --din[id[j]] == 0)q.push(id[j]);
if (dist[j] > dist[t.y] + w[i])
{
dist[j] = dist[t.y] + w[i];
if (id[j] == id[t.y])heap.push({ dist[j],j });
}
}
}
}
void topsort()
{
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
for (int i = 1; i <= bcnt; i++)
if (!din[i])q.push(i);
while (q.size())
{
auto t = q.front();
q.pop();
dijkstra(t);
}
}
int main()
{
cin >> n >> mr >> mp >> s;
memset(h, -1, sizeof h);
while (mr--)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
for (int i = 1; i <= n; i++)
{
if (!id[i])
{
bcnt++;
dfs(i, bcnt);
}
}
while (mp--)
{
int a, b, c;
cin >> a >> b >> c;
din[id[b]]++;
add(a, b, c);
}
topsort();
for (int i = 1; i <= n; i++)
{
if (dist[i] > 0x3f3f3f3f / 2)puts("NO PATH");
else cout << dist[i] << endl;
}
return 0;
}