P1144 最短路计数

题意：求出起点到各个点的最短路条数。

Solution：在堆优化dij的过程中维护每个点的最短路条数数组，如果严格小于就赋值，如果等于就累加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct edge{int v,w;};
vector<edge>e[N];
void add(int u,int v,int w){
	e[u].push_back({v,w});
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;cin>>u>>v;
		add(u,v,1);add(v,u,1);
		
	}
	vector<int>d(n+1,inf);vector<int>vis(n+1,0);
	vector<int>ad(n+1,0);
	priority_queue<pii,vector<pii>,greater<pii>>q;
	d[1]=0;q.push({0,1});ad[1]=1;
	while(q.size()){
		auto[dis,u]=q.top();q.pop();
		if(vis[u])continue;
		vis[u]=true;
		for(auto[v,w]:e[u]){
		if(d[v]>d[u]+w){
			d[v]=d[u]+w;
			q.push({d[v],v});
			ad[v]=ad[u];
		}
		else if(d[v]==d[u]+w){
			ad[v]+=ad[u];ad[v]%=mod;
			q.push({d[v],v});
		}
	}
	}
	for(int i=1;i<=n;i++){
		if(ad[i])cout<<ad[i]<<endl;
		else cout<<0<<endl;
		
	}
}

天梯赛L2-1紧急救援https://pintia.cn/problem-sets/994805046380707840/exam/problems/994805073643683840?type=7&page=0

题意：给出一张无向图，给定起点终点，求最短路条数，每个点有点权，输出点权和最大的最短路路径信息。

Solution：考虑dij过程中记录前驱信息，等价于dp过程中找最优方案。在最短路相等的时候，再判断点权和能不能更新，如果能变大，则更新点权和数组和前驱。

Ddbug:输入下标从0开始的时候，一定要警惕，最好自己写注释里，防止忘掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
struct edge{
	int v,w;
};
int S,T;
vector<edge>e[N];
void solve(){
	cin>>n>>m>>S>>T;
//编号0-n-1
//S++;T++;
	for(int i=0;i<=n-1;i++)cin>>a[i];
	for(int i=1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;
		//u++;v++;
		e[u].push_back({v,w});
		e[v].push_back({u,w});
	}
	vector<int>ad(n+1,0);
	vector<int>pre(n+1);
	vector<int>d(n+1,inf);
	vector<bool>vis(n+1,0);
	vector<int>f(n+1,0);
	auto dij=[&](){
		priority_queue<pii,vector<pii>,greater<pii>>q;
		d[S]=0;q.push({0,S});f[S]=a[S];ad[S]=1;
		while(q.size()){
			auto [dis,u]=q.top();q.pop();
			if(vis[u])continue;
			vis[u]=true;
			for(auto [v,w]:e[u]){
				if(d[v]>d[u]+w){
					d[v]=d[u]+w;
					q.push({d[v],v});
					pre[v]=u;
					f[v]=f[u]+a[v];
					ad[v]=ad[u];
				}
				else if(d[v]==d[u]+w){
					if(f[v]<f[u]+a[v]){
						pre[v]=u;	
						q.push({d[v],v});
						f[v]=f[u]+a[v];
						//ad[v]+=ad[u];
					}
					//q.push({d[v],v});
					ad[v]+=ad[u];
				}
			}
		}
	};
	dij();
	cout<<ad[T]<<" "<<f[T]<<endl;
	vector<int>v;
	for(int i=T;i!=S;i=pre[i])v.push_back(i);
	reverse(v.begin(),v.end());
	cout<<S<<" ";
	for(int i=0;i<v.size()-1;i++)cout<<v[i]<<" ";
	cout<<v.back();
	//cout<<S;
}