Pagini recente » Cod sursa (job #1124774) | Istoria paginii runda/cariera_1/clasament | vs | Cod sursa (job #46372) | Cod sursa (job #2153550)
#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;
}