Cod sursa(job #1106761)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 13 februarie 2014 09:49:10
Problema Ubuntzei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define Nmax 2009
#define Kmax 20
#define oo 2000000000
#define x first
#define c second
#define pb push_back
#define mp make_pair
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");

int N,M,K,gigel[Kmax],S,T;
int d[Kmax][Nmax];
vector<pair<int,int> >G[Nmax];
//dist[i][Nmax], i>0, distanta de la ubuntelul i la restu
struct cmp
{
    bool operator()(const int &a,const int &b)
    {
        return d[T][a]>d[T][b];
    };
};

priority_queue< int , vector < int > , cmp > pq;

void Dijkstra(int S)
{
    if(S)T=S;
    for(int i=0;i<=N;++i)d[T][i]=oo;
    d[T][S]=0;
    for( pq.push(S) ; !pq.empty() ; pq.pop())
    {
        int node=pq.top();
        for(vector<pair<int,int> >::iterator it=G[node].begin();it!=G[node].end();++it)
            if(d[T][it->x]>d[T][node]+it->c)
            {
                d[T][it->x]=d[T][node]+it->c;
                pq.push(it->x);
            }

    }
}
int main()
{
    f>>N>>M>>K;
    for(int i=1;i<=K;++i)f>>gigel[i];
    for(int i=1;i<=M;++i)
    {
        int x,y,c;
        G[x].pb(mp(y,c)),G[y].pb(mp(x,c));
    }
    S=1;T=0;
    Dijkstra(S);
    if(!K)
    {
        g<<d[0][N]<<'\n';
        return 0;
    }

    f.close();g.close();
    return 0;
}