題目鏈接:https://vijos.org/p/1285

背景

發(fā)完了k張照片，佳佳卻得到了一個(gè)壞消息：他的MM得病了！佳佳和大家一樣焦急萬(wàn)分！治好MM的病只有一種辦法，那就是傳說(shuō)中的0號(hào)藥水……怎么樣才能得到0號(hào)藥水呢？你要知道佳佳的家境也不是很好，成本得足夠低才行……

題目描述

得到一種藥水有兩種方法：可以按照魔法書上的指導(dǎo)自己配置，也可以到魔法商店里去買——那里對(duì)于每種藥水都有供應(yīng)，雖然有可能價(jià)格很貴。在魔法書上有很多這樣的記載：1份A藥水混合1份B藥水就可以得到1份C藥水。（至于為什么1+1=1，因?yàn)椤@是魔法世界）好了，現(xiàn)在你知道了需要得到某種藥水，還知道所有可能涉及到的藥水的價(jià)格以及魔法書上所有的配置方法，現(xiàn)在要問(wèn)的就是：1.最少花多少錢可以配制成功這種珍貴的藥水；2.共有多少種不同的花費(fèi)最少的方案（兩種可行的配置方案如果有任何一個(gè)步驟不同則視為不同的）。假定初始時(shí)你手中并沒(méi)有任何可以用的藥水。

輸入格式

第一行有一個(gè)整數(shù)N(N<=1000)，表示一共涉及到的藥水總數(shù)。藥水從0~N-1順序編號(hào)，0號(hào)藥水就是最終要配制的藥水。

第二行有N個(gè)整數(shù)，分別表示從0~N-1順序編號(hào)的所有藥水在魔法商店的價(jià)格（都表示1份的價(jià)格）。

第三行開始，每行有3個(gè)整數(shù)A、B、C，表示1份A藥水混合1份B藥水就可以得到1份C藥水。注意，某兩種特定的藥水搭配如果能配成新藥水的話，那么結(jié)果是唯一的。也就是說(shuō)不會(huì)出現(xiàn)某兩行的A、B相同但C不同的情況。

輸出格式

輸出兩個(gè)用空格隔開的整數(shù)，分別表示得到0號(hào)藥水的最小花費(fèi)以及花費(fèi)最少的方案的個(gè)數(shù)。

樣例輸入

7
10 5 6 3 2 2 3
1 2 0
4 5 1
3 6 2

樣例輸出

10 3

限制

1秒

提示

最優(yōu)方案有3種，分別是：直接買0號(hào)藥水；買4號(hào)藥水、5號(hào)藥水配制成1號(hào)藥水，直接買2號(hào)藥水，然后配制成0號(hào)藥水；買4號(hào)藥水、5號(hào)藥水配制成1號(hào)藥水，買3號(hào)藥水、6號(hào)藥水配制成2，然后配制成0。

解題思路

這是一道最短路的變形題。我們用val[i]來(lái)表示藥水i的價(jià)格、map[i][j]表示i和j可以合成的藥水、cnt[i]表示得到藥水i
的方案數(shù)。跑一遍Dijkstra算法，在松弛價(jià)格的時(shí)候，一定是vis[j]==1的時(shí)候，因?yàn)橐欢ㄒ盟幩甹的最小價(jià)格來(lái)更新。
當(dāng)val[map[k][j]]>val[k]+val[j]時(shí)，map[k][j]的方案數(shù)是k的方案數(shù)乘以j的方案數(shù)。
當(dāng)val[map[k][j]]==val[k]+val[j]時(shí)，map[k][j]的方案數(shù)是加上k的方案數(shù)乘以j的方案數(shù)。

#include <stdio.h> const int inf = 1e9; int map[1010][1010], val[1010], cnt[1010], vis[1010]; int main() {int n, a, b, c, k = 0, minn;scanf("%d", &n);for (int i = 0; i < n; i++){cnt[i] = 1;vis[i] = 0;for (int j = 0; j < n; j++)map[i][j] = -1;}for (int i = 0; i < n; i++)scanf("%d", &val[i]);while (~scanf("%d%d%d", &a, &b, &c))map[a][b] = map[b][a] = c;for (int i = 0; i < n; i++){minn = inf;for (int j = 0; j < n; j++)if (!vis[j] && minn > val[j])minn = val[k = j];vis[k] = 1;for (int j = 0; j < n; j++){if (vis[j] && map[k][j] != -1){if (val[map[k][j]] > val[k] + val[j])val[map[k][j]] = val[k] + val[j], cnt[map[k][j]] = cnt[k] * cnt[j];else if (val[map[k][j]] == val[k] + val[j])cnt[map[k][j]] += cnt[k] * cnt[j];}} }printf("%d %d\n", val[0], cnt[0]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的Vijos - 佳佳的魔法药水(最短路)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。