洛谷 P1875 佳佳的魔法药水

题目传送门

类似Dijkstra的思想,每次找到花费最少的那个点i,然后找到所有能和i组合且已经已经被更新成花费最小的点更新其他点.

方案数的话,运用乘法原理.

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

using namespace std;

int n,a[1101],y,x,z,g[1001][1001],ans[1001];
bool vis[1001];

inline void dij() {
	for(int i = 1;i < n; i++) {
		int mx = 999999999,id;
		for(int j = 0;j < n; j++)
			if(!vis[j] && a[j] < mx)
				id = j,mx = a[j];
		vis[id] = 1;
		for(int j = 0;j < n; j++)
			if(g[id][j] != -1 && vis[j]) {
				if(a[id] + a[j] < a[g[id][j]]) {
					ans[g[id][j]] = ans[id] * ans[j];
					a[g[id][j]] = a[id] + a[j];
					continue;
				}
				if(a[id] + a[j] == a[g[id][j]])
					ans[g[id][j]] += ans[id] * ans[j];
			}
	}
}

int main() {
	scanf("%d",&n);
	memset(g,-1,sizeof(g));
	for(int i = 1;i <= n; i++) {
		scanf("%d",&a[i-1]);
		ans[i-1] = 1;
	}
	while(scanf("%d%d%d",&x,&y,&z) != EOF) {
		g[x][y] = z;
		g[y][x] = z;
	}
	dij();
	printf("%d %d",a[0],ans[0]);
	return 0;
}