Pagini recente » Cod sursa (job #2375866) | Cod sursa (job #236299) | Cod sursa (job #1631230) | Cod sursa (job #802471) | Cod sursa (job #1106761)
#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;
}