Editorial for Islands

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Türkçe

Problemi Dijkstra'nın algoritmasını bir miktar düzenleyerek çözebiliriz. En başta priority queue'ya başlangıç noktası yerine tüm ANANAS adalarını 0 ağırlığı ile ekleriz. Bu şekilde bir ANANAS adasından çıkıp KIWI adalarına en kısa mesafeyi bulabiliriz.

Bundan sonra aynı algoritmayı bir kez daha kullanarak bu sefer KIWI adalarına geldiğimiz mesafeleri kullanarak KIWI adalarını priority queue'ya ekleyerek bu sefer MANGO adalarına olabilecek en kısa mesafeleri bulabiliriz. Bunlardan en kısası da soruda beklenen cevap.

English

We can solve the problem by slightly modifying the Dijkstra's algorithm. First of all, We add all of the ANANAS islands to the priority queue with 0 priority. In that way, we can find the shortest distance from the ANANAS islands to the KIWI islands.

From that point, we can use the same algorithm again. This time we will add the KIWI islands to the priority queue with the distances we obtained from the previous computation. Using that, we can find the shortest distance to the MANGO islands for each KIWI island. The smallest of those distances is the answer to the question.

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define fi first
#define se second

const int siz = 300005;

ll C[siz];
vector<pll> adj[siz];
vector<int> nodes[5];
ll distances[siz], distances2[siz];
ll n, m, a, b, c, w;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>c;
        nodes[c].pb(i);
        distances[i] = INT_MAX;
        distances2[i] = INT_MAX;
    }

    for(int i=0;i<m;i++) {
        cin>>a>>b>>w;
        adj[a].pb({b, w});
        adj[b].pb({a, w});
    }
    priority_queue<pll> pq;

    for(auto node: nodes[1]){
        distances[node] = 0;
        pq.push({0, node});
    }

    while(!pq.empty()){
        int node = pq.top().se;
        int dist = -pq.top().fi; pq.pop();

        for(auto x: adj[node]){
            if(distances[x.fi] > dist + x.se){
                distances[x.fi] = dist + x.se;
                pq.push({-distances[x.fi], x.fi});
            }
        }
    }

    for(auto node: nodes[2]){
        distances2[node] = distances[node];
        pq.push({-distances2[node], node});
    }

    while(!pq.empty()){
        int node = pq.top().se;
        int dist = -pq.top().fi; pq.pop();

        for(auto x: adj[node]){
            if(distances2[x.fi] > dist + x.se){
                distances2[x.fi] = dist + x.se;
                pq.push({-distances2[x.fi], x.fi});
            }
        }
    }


    ll res = INT_MAX;
    for(int i=0;i<nodes[3].size();i++){
        int node = nodes[3][i];
        if(distances2[node] < res) res = distances2[node];
    }

    if(res == INT_MAX) cout<<-1;
    else cout<<res;
}