Cod sursa(job #2153550)

Utilizator SkyConectorOvidiu Sonea SkyConector Data 6 martie 2018 12:04:36
Problema Ubuntzei Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define mp make_pair
#define pb push_back
using namespace std;
ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");
int n,m,k,cost[1002],curPoz,mini=1<<30;
vector<pair<int,int> > v[1002];
pair<int,int>x,pp;
vector<int>viz;
queue <int>q;
queue <pair<int,pair<vector<int> ,int> > >w;
pair< int,pair<vector<int>,int> >aux;
void citire()
{
    fin>>n>>m>>k;
    for(int i=0;i<=n;i++)
        viz.pb(0);
    for(int i=0;i<k;i++)
    {
        int aux;
        fin>>aux;
        viz[aux]=1;
    }
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        fin>>a>>b>>c;
        v[a].pb(mp(b,c));
        v[b].pb(mp(a,c));
    }
}
void Bellman()
{
    int aux;
    for(int i=1;i<=n;i++)
        cost[i]=1<<30;
    cost[curPoz]=0;
    q.push(curPoz);
    while(!q.empty()){
        aux=q.front();
        q.pop();
        for(int i=0;i<v[aux].size();i++)
        {
            x=v[aux][i];
            if(cost[x.first]>cost[aux]+x.second)
            {
                cost[x.first]=cost[aux]+x.second;
                q.push(x.first);
            }
        }
    }
}
void calcRaspuns()
{
    //for(int i=1;i<=n;i++)
        //aux.second.first[i]=0;
    w.push(mp(1,mp(vector<int>(n+2),0)));
    for(int i=1;i<=n;i++)
        w.front().second.first[i]=0;
    while(w.empty()==false)
    {
        aux=w.front();
        w.pop();
        curPoz=aux.first;
        aux.second.first[curPoz]=1;
        Bellman();
        int ok=1;
        for(int i=1;i<n;i++)
        {
            if(viz[i]==1)
            {
                if(aux.second.first[i]==0)
                {
                    ok=0;
                    w.push(mp(i,mp(aux.second.first,cost[i]+aux.second.second)));
                }
            }
        }
        if(aux.second.second+cost[n]<=mini && ok==1)
        {
            mini=aux.second.second+cost[n];
        }
    }
    fout<<mini;
}
int main()
{
    citire();
    calcRaspuns();
    return 0;
}