相信的心是你的魔法 | 信じの心は君の魔法

題意：

• 藥水可以直接買，也可以由兩種其他藥水配置而來，問配置出 0號藥水 的最小價錢 和 最小價的方案數

思路：

• 義眼拓撲，但！在題意沒有明確強調 有向無環圖 時，用 拓撲 寫的沙口都會吃盡苦頭…
• 此題的數據是有環的，有環就代表得用最短路來寫；
• 但這個由兩個藥水推導出下一個藥水就很蛋痛，正常的最短路思維都是由一個最小推導其他
• 觀察數據范圍，除了 Floyd 都可用，圖中的邊權都為正，Dijkstra可用
• 明確 算法的本質 很重要，樸素版Dijkstra算法的貪心在此題的維護上非常方便，通過一個確定的最小來更新其他點的 dist 值

代碼：

#include<bits/stdc++.h> #include<unordered_set> #include<unordered_map> #define mem(a,b) memset(a,b,sizeof a) #define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)) #define sca scanf #define pri printf #define ul (u << 1) #define ur (u << 1 | 1) #define fx first #define fy second //#pragma GCC optimize(2) //[博客地址](https://blog.csdn.net/weixin_51797626?t=1) using namespace std;typedef long long ll; typedef pair<ll, int> PII; typedef pair <ll, PII> PI;const int N = 1010, M = 4000010, MM = N; int INF = 0x3f3f3f3f, mod = 100003; ll LNF = 0x3f3f3f3f3f3f3f3f; int n, m, k, T, S, D; int way[N][N], cost[N], cnt[N]; bool st[N];int main() {cinios;cin >> n;for (int i = 1; i <= n; i++)cin >> cost[i], cnt[i] = 1;//初始每個藥水都有花費，方案數最少為 1int a, b, x;while (cin >> a >> b >> x){a++, b++, x++;way[a][b] = x;//記錄組合：原料兩藥水 + 配得的藥水way[b][a] = x;}for (int i = 1; i <= n; i++) { //標準Dijkstraint t = 0;for (int j = 1; j <= n; j++)if (!st[j] && (!t || cost[j] < cost[t]))//貪心取出花費最小的一個藥水t = j;st[t] = true;//圖中的邊權都是正，拿出來的點必定已經被確定了，花費不能更小for (int j = 1; j <= n; j++) { //魔改部分int c = way[t][j];//枚舉此藥水與其他藥水的所有匹配方案if (st[j] && c) {//當且僅當有匹配，且兩藥水都是被確定過（花費已經是最小）時if (cost[c] > cost[t] + cost[j]) {cost[c] = cost[t] + cost[j];//更新目標藥水cnt[c] = cnt[t] * cnt[j];}else if (cost[c] == cost[t] + cost[j])//同時記錄方案cnt[c] += cnt[t] * cnt[j];}}}cout << cost[1] << " " << cnt[1];return 0; } /* */

總結

以上是生活随笔為你收集整理的洛谷：P1875 佳佳的魔法药水（有向有环图 + Dijkstra变式）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。