文章

25

粉丝

0

获赞

0

访问

68498

头像
最短路径树(SPT)
经验总结
发布于2020年4月13日 23:25
阅读数 6873

(1)最短路径树和最小生成树的区别:

最短路径树:源点到其它所有节点的最短路径构成的树。实际上是一个(DAG)

最小生成树:网络中任意两个顶点可达,且边集总长度最小,不能保证源点到其它点距离最小。

(2)求最短路径树的数量:乘法原理(记录每个节点的父节点可取数cnt[i]表示i号节点可取父节点)

则SPT数量为: cnt[1]*cnt[2]*....cnt[n]

(ans*=cnt[i]%MOD)!=(ans=ans*cnt[i]%MOD)

#include<iostream>
#include<queue>
using namespace std;
int n, m;
const int MAXN = 1010;
const int MAXE = 2010;
const int MOD = 2147483647;
int cnt[MAXN];
struct edge{
	int from, to, weight;
	int next;//指向下一个节点
}Edge[MAXE];
int idx = 0, h[MAXN];
void add(int a, int b, int c){
	Edge[++idx].from = a;
	Edge[idx].to = b;
	Edge[idx].weight = c;
	Edge[idx].next = h[a];
	h[a] = idx;
}

struct node{
	int u, d;//从源点到u的最短路径
	bool operator <(const node a)const{
		return d>a.d;
	}
};
int dis[MAXN];
void dijkstra(){
	memset(dis, 0x3f3f3f3f, sizeof dis);
	priority_queue<node>q;
	q.push({ 1, 0 });
	dis[1] = 0;
	while (q.size()){
		node now = q.top();
		q.pop();

		for (int i = h[now.u]; i; i = Edge[i].next){
			if (dis[Edge[i].to] > dis[now.u] + Edge[i].weight){
				dis[Edge[i].to] = dis[now.u] + Edge[i].weight;
				q.push({ Edge[i].to, dis[Edge[i].to] });
			}
		}
	}
}

int main(){
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int x, y, w;
		cin >> x >> y >> w;
		add(x, y, w);
		add(y, x, w);
	}

	dijkstra();

	for (int i = 1; i <= n; i++){
		for (int j = h[i]; j; j = Edge[j].next){
			if (dis[Edge[j].to] == dis[i] + Edge[j].weight){
				cnt[Edge[j].to]++;
			}
		}
	}

	int ans = 1;
	for (int i = 2; i <= n; i++){
		//ans *= cnt[i];
		ans = ans*cnt[i] % MOD;
	}
	cout << ans << endl;

	return 0;
}

 

 



登录后发布评论

暂无评论,来抢沙发