Pagini recente » Cod sursa (job #311783) | Cod sursa (job #1695081) | Cod sursa (job #2778761) | Cod sursa (job #479411) | Cod sursa (job #1075123)
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
#define Nmax 2001
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
int n,m,i,a,b,c,k,kv[Nmax],sum;
vector<int> v[Nmax],w[Nmax];
struct muchie{int t,a,b;};
class Compare {
public:
bool operator()(muchie& t1, muchie& t2)
{
if (t1.t > t2.t) return true;
return false;
}
};
priority_queue<muchie, vector<muchie>, Compare> cd;
int djk(int s)
{
muchie u;
int i,e;
int viz[Nmax],dr[Nmax];
for(i=1;i<=n;i++) viz[i]=dr[i]=0;
e=v[s].size();
for(i=0;i<e;i++) if(viz[v[s].at(i)]==0)
{
u.a=s;
u.b=v[s].at(i);
u.t=w[s].at(i)+dr[s];
cd.push(u);
}
viz[s]=1;
while(!cd.empty())
{
if(kv[s]==0)
{
//g<<cd.top().a<<","<<cd.top().b<<" -> "<<cd.top().t<<"\n";
s=cd.top().b;
if(viz[s]==0)
{
dr[s]=cd.top().t;
cd.pop();
e=v[s].size();
for(i=0;i<e;i++) if(viz[v[s].at(i)]==0)
{
u.a=s;
u.b=v[s].at(i);
u.t=w[s].at(i)+dr[s];
cd.push(u);
}
}
else cd.pop();
viz[s]=1;
}
else cd.pop();
}
if(k==0) sum+=dr[n];
else sum+=dr[s];
k--;
kv[s]=0;
//for(i=1;i<=n;i++) g<<dr[i]<<" ";g<<"\n";
//if(k!=-1) g<<s<<" = "<<dr[s]<<"\n";
//else g<<n<<" = "<<dr[n]<<"\n";
return s;
}
int main()
{
f>>n>>m;
f>>k;
for(i=1;i<=k;i++)
{
f>>a;
kv[a]=1;
}
for(i=1;i<=m;i++)
{
f>>a>>b>>c;
v[a].push_back(b);
w[a].push_back(c);
v[b].push_back(a);
w[b].push_back(c);
}
int q=1;
while(k>0)
{
//g<<q<<" -> ";
q=djk(q);
}
//g<<q<<" -> ";
djk(q);
g<<sum<<"\n";
f.close();
g.close();
return 0;
}