Cod sursa(job #893741)

Utilizator Sm3USmeu Rares Sm3U Data 26 februarie 2013 17:38:05
Problema Ubuntzei Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <cstdio>
#include <vector>
#include <queue>

#define nMax 2010
#define oo 1<<30
#define min(a,b) ((a<b)?a:b)

using namespace std;

struct drum{
    int catre;
    int cost;
    drum (int ca, int co){
        catre = ca;
        cost = co;
    }
};

int costuri[nMax][nMax];
int nodCurent;

struct cmp{
    bool operator () (const int &a, const int &b)const{
        return costuri[nodCurent][a] < costuri[nodCurent][b];
    }
};

priority_queue <int, vector<int>, cmp> q;
vector <drum> graf[nMax];
int orase[nMax];
int nrOrase;
int n;
int sol[nMax][nMax];
/**
    sol[i][j] = drumul de la 1 la j trecand prin i orase,
        i >= j;
*/

void citire(){
    int m;
    scanf("%d", &n);
    scanf("%d", &m);
    scanf("%d", &nrOrase);
    for (int i = 1; i <= nrOrase; ++ i){
        scanf("%d", &orase[i]);
    }
    while (m --){
        int deLa;
        int catre;
        int cost;
        scanf("%d %d %d", &deLa, &catre, &cost);
        graf[deLa].push_back(drum(catre, cost));
        graf[catre].push_back(drum(deLa, cost));
    }
}

void dijkstra(int nod){
    nodCurent = nod;
    for(int i = 1; i <= n; ++ i){
       costuri[nod][i] = oo;
    }
    costuri[nod][nod] = 0;
    q.push(nod);
    while(!q.empty()){
        nod = q.top();
        q.pop();
        for (unsigned int i = 0; i < graf[nod].size(); ++ i){
            if(costuri[nodCurent][graf[nod][i].catre] > costuri[nodCurent][nod] + graf[nod][i].cost){
                costuri[nodCurent][graf[nod][i].catre] = costuri[nodCurent][nod] + graf[nod][i].cost;
                q.push(graf[nod][i].catre);
            }
        }
    }
}

void rezolvare(){
    for(int i = 1; i <= n; ++ i){
        dijkstra(i);
    }
    for(int i = 2; i <= nrOrase; ++ i){
        sol[2][i] = costuri[1][orase[i - 1]];
    }
    sol[2][nrOrase + 1] = costuri[1][orase[nrOrase]];
    sol[2][nrOrase + 2] = costuri[1][n];

    for (int i = nrOrase + 1; i >= 1; -- i){
        orase[i] = orase[i - 1];
    }
    orase[1] = 1;
    orase[nrOrase + 2] = n;
    nrOrase += 2;
    for(int i = 3; i <= nrOrase; ++ i){
        for(int j = i; j <= nrOrase; ++ j){
            sol[i][j] = oo;
            for (int k = i - 1; k < j; ++ k){
                sol[i][j] = min(sol[i][j], sol[i - 1][k] + costuri[orase[k]][orase[j]]);
                sol[i][j] = min(sol[i][j], sol[i - 1][j] + 2 * costuri[orase[k]][orase[j]]);
            }
        }
    }
    printf ("%d\n", sol[nrOrase][nrOrase]);
}

int main()
{
    freopen("ubuntzei.in", "r", stdin);
    freopen("ubuntzei.out", "w", stdout);

    citire();
    rezolvare();

    return 0;
}