Pagini recente » Cod sursa (job #1922811) | Cod sursa (job #1532507) | Cod sursa (job #3240517) | Cod sursa (job #2589670) | Cod sursa (job #2654374)
#include <fstream>
#include<deque>
#include <bits/stdc++.h>
#include<math.h>
#include<queue>
using namespace std;
struct dr{int oras;int cost;};
int n,k,m,ubuntz[2001][1<<17],dorm[2001];
deque<dr>drum[10001];
struct pr{int oras;int om;};
struct compara
{
bool operator()(pr a1,pr a2)
{
return ubuntz[a1.om][a1.om]>ubuntz[a2.oras][a2.om];
}
};
priority_queue<pr,vector<pr>,compara>q;
int main()
{ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
f>>n>>m>>k;
for(int i=1;i<k+1;i++)
{
int yy;
f>>yy;
dorm[yy]=i;
}
for(int i=1;i<=m;i++)
{int x,y,cost;
f>>x>>y>>cost;
dr pus;pus.oras=y;pus.cost=cost;
drum[x].push_front(pus);
pus.oras=x;
drum[y].push_front(pus);
}
ubuntz[1][0]=-1;
q.push({1,0});
while(!q.empty())
{
pr pac=q.top();
int oras=pac.oras;
int omuleti=pac.om;
q.pop();
for(int i=1;i<=drum[oras].size();i++)
{
dr nou=drum[oras].front();drum[oras].push_back(drum[oras].front());drum[oras].pop_front();
int nou_oras=nou.oras;int nou_cost=nou.cost;
if(dorm[nou_oras]!=0&&((omuleti&(1<<dorm[nou_oras]))==0))
{
if((ubuntz[nou_oras][omuleti+(1<<dorm[nou_oras])]>ubuntz[oras][omuleti]+nou_cost+(ubuntz[oras][omuleti]==-1?1:0))||ubuntz[nou_oras][omuleti+(1<<dorm[nou_oras])]==0)
{
ubuntz[nou_oras][omuleti+(1<<dorm[nou_oras])]=ubuntz[oras][omuleti]+nou_cost+(ubuntz[oras][omuleti]==-1?1:0);
q.push({nou_oras,omuleti+(1<<dorm[nou_oras])});
}
}
else
if((ubuntz[nou_oras][omuleti]>ubuntz[oras][omuleti]+nou_cost+(ubuntz[oras][omuleti]==-1?1:0))||ubuntz[nou_oras][omuleti]==0)
{
ubuntz[nou_oras][omuleti]=ubuntz[oras][omuleti]+nou_cost+(ubuntz[oras][omuleti]==-1?1:0);
q.push({nou_oras,omuleti});
}
}
}
int uu=1;
for(int i=1;i<=k;i++)
uu*=2;
g<<ubuntz[n][uu];
return 0;
}