Pagini recente » Cod sursa (job #1495219) | Cod sursa (job #1045663) | Cod sursa (job #3163985) | Cod sursa (job #2301842) | Cod sursa (job #2864060)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int> utHossz;
int n,m,k;
bool vanBaratAvarosban[2001]={false};
vector<utHossz> terkep[2001];
int d[2001];
bool elemeAzOptSornak[2001]={false};
struct osszehasonlitas{
bool operator()(int x,int y)
{
return d[x]>d[y];
}
};
priority_queue<int, vector<int>,osszehasonlitas> optimalizalandoElemek;
void beolvas()
{
ifstream fin("ubuntzei.in");
fin>>n>>m>>k;
int a,b,c;
for(int i=1;i<=k;i++)
{
fin>>a;
vanBaratAvarosban[a]=true;
}
for(int i=1;i<=m;i++)
{
fin>>a>>b>>c;
terkep[a].push_back(make_pair(b,c));
terkep[b].push_back(make_pair(a,c));
}
fin.close();
}
void dijkstra(int kezdoCsucs)
{
for(int i=1;i<=n;i++)
{
d[i]=99999;
}
d[kezdoCsucs]=0;
optimalizalandoElemek.push(kezdoCsucs);
elemeAzOptSornak[kezdoCsucs]=true;
while(!optimalizalandoElemek.empty())
{
int csucs=optimalizalandoElemek.top();
optimalizalandoElemek.pop();
elemeAzOptSornak[csucs]=false;
for(size_t i=0;i<terkep[csucs].size();i++)
{
int szomszed=terkep[csucs][i].first;
int tavolsag=terkep[csucs][i].second;
if(d[csucs]+tavolsag<d[szomszed])
{
d[szomszed]=d[csucs]+tavolsag;
if(!elemeAzOptSornak[szomszed])
{
optimalizalandoElemek.push(szomszed);
elemeAzOptSornak[szomszed]=1;
}
}
}
}
}
int main() {
int l=0;
beolvas();
dijkstra(1);
int mini,miniIn;
while(true)
{
mini=999999;
for(int i=1;i<=n;i++)
{
if(vanBaratAvarosban[i]&&d[i]<mini)
{
mini=d[i];
miniIn=i;
}
}
if(mini!=999999) {
l += mini;
vanBaratAvarosban[miniIn] = false;
}
else
{
break;
}
}
dijkstra(miniIn);
l+=d[n];
ofstream fout("ubuntzei.out");
fout<<l;
fout.close();
return 0;
}