算法流程
样例
一些思考
dijkstra算法不能有负权边,所以更新时只能把正权边入堆。而遇到负权边时,也能更新dist数组,但不入堆。
按照拓扑序进行连通块内的dijkstra算法,保证了拓扑排列,在源点S所在的连通块后的所有连通块都能被更新, 所以算出的路径也还是最短的路径
时间复杂度
O(mlogn),m为边的数,n为顶点数
C++ 代码
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
const int N = 25010, M = 150010, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];
int n, mr, mp, s;
//id:点所在的连通块号, bcnt:连通块数量
int id[N], bcnt;
//连通块的入度数组
int deg[N];
vector<int> block[N];
int q[N], hh, tt = -1;
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)
{
block[bcnt].push_back(u);
id[u] = bcnt;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(!id[j]) dfs(j);
}
}
void dijkstra(int block_id)
{
priority_queue<PII, vector<PII>, greater<PII>> heap;
//取出该连通块所有的点, 入堆
for(int u : block[block_id])
{
heap.push({dist[u], u});
}
while(heap.size())
{
PII t = heap.top();
heap.pop();
int u = t.second;
if(st[u]) continue;
st[u] = true;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[u] + w[i])
{
dist[j] = dist[u] + w[i];
if(id[j] == block_id) heap.push({dist[j], j});
}
if(id[j] != block_id && --deg[id[j]] == 0) q[++tt] = id[j];
}
}
}
void topoSort()
{
//dist赋初值
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
//入度为0的连通块入队列
for(int i = 1; i <= bcnt; i++)
{
if(!deg[i]) q[++tt] = i;
}
while(hh <= tt)
{
int t = q[hh++];
dijkstra(t);
}
}
int main()
{
scanf("%d%d%d%d", &n, &mr, &mp, &s);
memset(h, -1, sizeof h);
for(int i = 0; i < mr; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
//建立所有的连通块
for(int i = 1; i <= n; i++)
{
if(!id[i]) {
++bcnt;
dfs(i);
}
}
//在连通块之间建边
for(int i = 0; i < mp; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), deg[id[b]]++;
}
//算法开始
topoSort();
for(int i = 1; i <= n; i++)
{
if(dist[i] > INF / 2) puts("NO PATH");
else printf("%d\n", dist[i]);
}
return 0;
}
之前一直不理解,一个连通块有2个入边,而且是两个不同的连通块的入边,会不会被做次dijkstra。而第一次dijkstra的时候已经把这个连通块内的所有点更新完了,并打上了标记,第二条入边的时候,连通块在跑dijkstra的时候,更新不了。
后来想了一下,一个连通块在做dijkstra的时候,如果有两个不同的模块的入边,这两个模块一定在topu队列的前面,所以,一个模块在做dijkstra之前,这个模块内点的d数组一定更新完了。
所以,算法应该没问题。
你是对的,如是前序依赖存在,是不能跑dijkstra的,只有所有前序清晰,才能开始跑最短路,感觉有点像无后序性,DP?
记录美好生活
有个小瑕疵:if(dist[i] > INF / 2) puts(“NO PATH”);
应该改成 >=1e9 因为题目要求的dist最大是为1e9,是超过了INF/2的。这题数据水了点才过了
你太棒了博主我一开始用队列过不了用双端队列就过了真的吊
%%%%%%%%%%
有用并查集写的吗?
太强了
大佬们,请教一个问题,根据这个样例,既然1,2点不可达,那么可不可以直接把起点所在的连通块入度置为0,然后从这个团开始做拓扑排序呢?
可以,但是也要把其它入度为0的连通块一起入队,所以没太大区别
可是我对这题有个问题:有没有考虑 起始点之间存在多条拓扑序 的情况?是不是需要把起始点间的所有的拓扑序列都求出来,然后取min?
多条拓扑序任取一条扫描得到的最短路是一样的
对,只要前后关系确定,具体走哪个拓扑序都是一样的。比如DP 打表,遍历序并不唯一。
太强了,学习了
bang
棒
qwq
样例的图 连通块三画错惹
谢谢!样例解析好棒啊!