Zadaca Portali

Smetam deka ovaa zadaca se resava so dijkstra , no sakam nekoj da mi dade podetalna ideja.
http://mendo.mk/Task.do?id=707

BATIR wrote:Smetam deka ovaa zadaca se resava so dijkstra , no sakam nekoj da mi dade podetalna ideja.
http://mendo.mk/Task.do?id=707

Пробај сам/а прво да ја решиш, види што е проблемот (дали е пребавно или нешто друго), па потоа може да ти помогнеме. Така најдобро ќе научиш.
За задачава, да, може да се искористи Dijkstra. Пробај и да го искористиш фактот што има само 10 типови на портали.

Еве ти и решение ако заглавиш, ама ти препорачувам да не го гледаш додека не пробаш сам/а.

#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int N, V;
    cin >> N >> V;

vector<int> T(N + 1);
    for (int i=1; i<=N; i++) {
        cin >> T[i];
    }

int dist[N + 1];
    fill(dist, dist+N+1, 2100000000);

//ako iskoristime portal od nekoj tip
    //ne mora potoa voopshto da go gledame
    //(bidejki kaj Dijkstra, vekje sme go
    //iskoristile od grad so pomalo rastojanie)
    bool used[11];
    fill(used, used+11, false);

dist[1] = 0;
    priority_queue<pair<int, int> > pq;
    pq.push({0, 1});

int dx[] = {-1, 1};

while (!pq.empty()) {
        auto state = pq.top();
        pq.pop();

int location = state.second;

//move left or right
        for (int m=0; m<2; m++) {
            int next = location+dx[m];

if (next >= 1 && next <= N) {
                if (dist[next] > dist[location] + 1) {
                    dist[next] = dist[location] + 1;
                    pq.push({-dist[next], next});
                }
            }
        }

//use a portal
        if (used[T[location]] == false) {
            used[T[location]] = true;

for (int next=1; next <= N; next++) {
                if (T[location] == T[next]) {

if (dist[next] > dist[location] + V) {
                        dist[next] = dist[location] + V;
                        pq.push({-dist[next], next});
                    }
                }
            }
        }
    }

cout << dist[N] << endl;
    return 0;
}