Code

[{"language":"C++","code":"class Solution {\npublic:\n    using pii = pair<long long, int>;\n    vector<long long> dijkstra(int n, vector<vector<pii>>& graph, int src) {\n        vector<long long> dist(n, LLONG_MAX);\n        priority_queue<pii, vector<pii>, greater<pii>> pq;\n        dist[src] = 0;\n        pq.push({0, src});\n        while (!pq.empty()) {\n            auto [d, u] = pq.top(); pq.pop();\n            if (d > dist[u]) continue;\n            for (auto& [v, w] : graph[u]) {\n                if (dist[v] > d + w) {\n                    dist[v] = d + w;\n                    pq.push({dist[v], v});\n                }\n            }\n        }\n        return dist;\n    }\n    int minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2, int dest) {\n        vector<vector<pii>> g(n), rg(n);\n        for (auto& e : edges) {\n            g[e[0]].push_back({e[1], e[2]});\n            rg[e[1]].push_back({e[0], e[2]});\n        }\n        auto d1 = dijkstra(n, g, src1);\n        auto d2 = dijkstra(n, g, src2);\n        auto dd = dijkstra(n, rg, dest);\n        long long ans = LLONG_MAX;\n        for (int i = 0; i < n; ++i) {\n            if (d1[i] == LLONG_MAX || d2[i] == LLONG_MAX || dd[i] == LLONG_MAX) continue;\n            ans = min(ans, d1[i] + d2[i] + dd[i]);\n        }\n        return ans == LLONG_MAX ? -1 : ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    using</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> pii</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> =</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> pair</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">long</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> long</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">>;</span></span>\n<span class=\"line\"><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">    vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">long</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> long</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">> </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">dijkstra</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> n</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">pii</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">>></span><span style=\"color:#D73A49;--shiki-dark:#
Related Tags
