Cod sursa(job #919454)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 19 martie 2013 17:46:58
Problema Gather Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.24 kb
#include <fstream>
#include <vector>
#define nmax 800
#define kmax 17
#define oo (1<<30)
#define pb push_back
#define mp make_pair
#define Vecin G[Nod][i].first
#define Dist G[Nod][i].second.first
#define Capacitate G[Nod][i].second.second
using namespace std;
 
vector < pair<int, pair<int,int> > > G[nmax];
vector <int> Detinut;
int N,M,K,Answer,D[kmax][kmax][kmax],DP[(1<<kmax)][kmax];
 
class HEAP {
     
    #define NMAxHeap nmax
    #define left(i) (i<<1)
    #define right(i) ((i<<1)+1)
    #define father(i) (i>>1)
    #define cmp(a,b) (A[V[a]]<A[V[b]])
     
    public:
        int V[NMAxHeap],A[NMAxHeap],Loc[NMAxHeap],Vf;
    public:
        HEAP():Vf(0){}
        void push(int,int);
        void pop();
        void update(int,int);
        int front();
        int size();
    private:
        void Up(int);
        void Down(int);
         
};
void HEAP::Up(int nod) {
     
    while(nod>1&&cmp(nod,father(nod))) {
        swap(V[nod],V[father(nod)]);
        swap(Loc[V[nod]],Loc[V[father(nod)]]);
        nod=father(nod);
        }
     
}
void HEAP::Down(int nod) {
     
    int son;
    do {
        son=0;
        if(left(nod)<=Vf) {
            son=left(nod);
            if(right(nod)<=Vf&&cmp(right(nod),son))
                son=right(nod);
            if(cmp(nod,son))
                son=0;
            }
         
        if(son) {
            swap(V[nod],V[son]);
            swap(Loc[V[nod]],Loc[V[son]]);
            nod=son;
            }
         
    }while(son);
     
}
void HEAP::push(int id,int Val) {
     
    V[++Vf]=id;
    A[id]=Val;
    Loc[id]=Vf;
    this->Up(Vf);
     
}
void HEAP::pop() {
     
    V[1]=V[Vf--];
    Loc[V[1]]=1;
    this->Down(1);
     
}
void HEAP::update(int id,int Val) {
     
    A[id]=Val;
    this->Up(Loc[id]);
    this->Down(Loc[id]);
     
}
int HEAP::front() {
     
    return V[1];
     
}
int HEAP::size() {
     
    return Vf;
     
}
 
HEAP Heap;
 
void Dijkstra(int Start,int FluxMin) {
     
    int i,Nod;
     
    for(i=1;i<=N;i++)
        Heap.A[i]=oo;
     
    Heap.push(Start,0);
     
    while(Heap.size()) {
         
        Nod=Heap.front();
        Heap.pop();
         
        for(i=0;i<G[Nod].size();i++)
            if(Capacitate >= FluxMin && Heap.A[Vecin] >= Heap.A[Nod]+Dist) {
                 
                if(Heap.A[Vecin] == oo)
                    Heap.push(Vecin,Heap.A[Nod]+Dist);
                else
                    Heap.update(Vecin,Heap.A[Nod]+Dist);
                 
                }
             
        }
     
}
void solve() {
     
    int i,j,k,Config,Nod,Vec;
     
    for(i=0;i<K;i++)
        for(j=0;j<K;j++) {
             
            Dijkstra(Detinut[i],j);
             
            for(k=0;k<K;k++)
                D[j][i][k]=(Heap.A[Detinut[k]]==oo?oo:(j+1)*Heap.A[Detinut[k]]);
             
            }
     
    Dijkstra(1,0);
     
    for(i=0;i<(1<<K);i++)
        for(j=0;j<K;j++)
            DP[i][j]=oo;
     
    for(i=0;i<K;i++)
        DP[(1<<i)][i]=Heap.A[Detinut[i]];
     
    for(Config=1;Config<(1<<K);Config++)
        for(Nod=0;Nod<K;Nod++)
            if(DP[Config][Nod]!=oo && Config&(1<<Nod)) {
                 
                for(k=0,i=Config;i;i&=(i-1),k++);
                 
                for(Vec=0;Vec<K;Vec++)
                    if(!(Config&(1<<Vec)) && D[k][Nod][Vec]!=oo)
                        DP[Config|(1<<Vec)][Vec]=min(DP[Config|(1<<Vec)][Vec],DP[Config][Nod]+D[k][Nod][Vec]);
                     
                }
     
    Answer=oo;
     
    for(i=0;i<K;i++)
        Answer=min(Answer,DP[(1<<K)-1][i]);
     
}
void read() {
 
    int i,x,y,c,d;
    ifstream in("gather.in");
    in>>K>>N>>M;
     
    for(i=1;i<=K;i++)
        in>>x,
        Detinut.pb(x);
         
    for(i=1;i<=M;i++) {
         
        in>>x>>y>>d>>c;
         
        G[x].pb(mp(y,mp(d,c)));
        G[y].pb(mp(x,mp(d,c)));
         
        }
     
    in.close();
     
}
void write() {
     
    ofstream out("gather.out");
    out<<Answer<<'\n';
    out.close();
     
}
int main() {
     
    read();
    solve();
    write();
     
    return 0;
     
}