「题解」佳佳的魔法药水

题目链接

Luogu P1875 佳佳的魔法药水

分析

初始的时候每个点的 $dis$ 为本身花费，$ans$ 为 $1$。

读入 $a, b, c$，则分别连 $a \stackrel{dis_{b}}{ \Rightarrow}c, b \stackrel{dis_{a}}{ \Rightarrow}c$，注意边权不要直接存，因为之后 dis 的数据有可能改变。

接下来跑 dijkstra，不同的地方在于更新的时候要两个药水都是已确定。

vector 过不了 hack 数据，不知道为什么，二维数组可以过。

更新：是因为正确性有问题。dijkstra 每次更新时，不仅要更新没访问过的 dis 最小的点，要连同已访问过的点一起更新。因为有可能当前这个点作为已访问过的点的出边的边权！

参考代码

vector：

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

const int N = 1e3 + 10;

int n;
int a, b, c;
long long dis[N]; // 最短路长度
long long ans[N]; // 计数
bool v[N]; // 是否已确定

struct edge{
	int to;
	int w;
};

vector <edge> g[N];

pair <long long, int> t; 

priority_queue <pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > q;

int main(){
	
	scanf("%d", &n);
	
	for(int i = 0; i < n; i++){
		scanf("%lld", &dis[i]);
		ans[i] = 1;
		q.push(make_pair(dis[i], i));
	}
	
	while(scanf("%d%d%d", &a, &b, &c) != EOF){
		g[a].push_back({c, b});
		if(a != b){ // 防止 A, B 相同的毒瘤数据
			g[b].push_back({c, a});
		}
	}
	
	while(!q.empty()){ // dijkstra
		t = q.top();
		q.pop();
		
		if(v[t.second]){
			continue;
		}
		
		v[t.second] = 1;
		
		for(auto i : g[t.second]){
			if(v[i.w]){ // 注意此处待合成的另一瓶药水也要已确定
				if(t.first + dis[i.w] == dis[i.to]){
					ans[i.to] += ans[t.second] * ans[i.w];
				}else{
					if(t.first + dis[i.w] < dis[i.to]){
						dis[i.to] = t.first + dis[i.w];
						ans[i.to] = ans[t.second] * ans[i.w];
						q.push(make_pair(dis[i.to], i.to));
					}
				}
			}
		}
	}
	
	printf("%lld %lld\n", dis[0], ans[0]);
	
	return 0;
}

二维数组：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>

using namespace std;

const int N = 1e3 + 10;

int n;
int a, b, c;
long long dis[N];
long long ans[N];
bool v[N];

int f[N][N]; // f[i][j] 为 i 和 j 可以合成的药水，不能合成则为 -1

pair <long long, int> t; 

priority_queue <pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > q;

int main(){
	
	scanf("%d", &n);
	
	for(int i = 0; i < n; i++){
		scanf("%lld", &dis[i]);
		ans[i] = 1;
		q.push(make_pair(dis[i], i));
	}
	
	memset(f, -1, sizeof(f));
	
	while(scanf("%d%d%d", &a, &b, &c) != EOF){
		f[a][b] = f[b][a] = c;
	}
	
	while(!q.empty()){
		t = q.top();
		q.pop();
		
		if(v[t.second]){
			continue;
		}
		
		v[t.second] = 1;
		
		for(int i = 0; i < n; i++){
			if(f[t.second][i] != -1 && v[i]){
				if(t.first + dis[i] == dis[f[t.second][i]]){
					ans[f[t.second][i]] += ans[t.second] * ans[i];
				}else{
					if(t.first + dis[i] < dis[f[t.second][i]]){
						dis[f[t.second][i]] = t.first + dis[i];
						ans[f[t.second][i]] = ans[t.second] * ans[i];
						q.push(make_pair(dis[f[t.second][i]], f[t.second][i]));
					}
				}
			}
		}
	}
	
	printf("%lld %lld\n", dis[0], ans[0]);
	
	return 0;
}