This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <climits>
using namespace std;
const int nmax=100005;
vector< pair<int,long long> > v[nmax];
long long d[nmax][32];
bool E[nmax][32];
int norm[nmax],imp[10];
long long di,newd,ans;
int x,n,m,nod,k,i,j,y,z,stare,stare_noua,orig;
struct node
{
long long D;
int node,state;
};
struct cmp
{
bool operator()(node unu,node doi)
{
return unu.D>doi.D;
}
};
priority_queue <node,vector<node>,cmp > pq;
void dij()
{
for(stare=1;stare<(1<<k);stare++)
{
for(x=1;x<=n;x++)
{
for(i=stare; i!=0; i=((i-1)&stare))
{
newd=1LL*d[x][i]+d[x][(stare-i)];
if(newd<d[x][stare])
{
d[x][stare]=newd;
}
}
if(d[x][stare]<1LL*1e17)
pq.push({d[x][stare],x,stare});
}
while(!pq.empty())
{
x=pq.top().node;
di=pq.top().D;
pq.pop();
if(stare==(1<<k)-1)
{
ans=di;
return;
}
if(!E[x][stare])
{
E[x][stare]=1;
for(i=0; i<v[x].size(); i++)
{
nod=v[x][i].first;
newd=v[x][i].second+di;
if(newd<d[nod][stare])
{
d[nod][stare]=newd;
pq.push({newd,nod,stare});
}
}
}
}
}
}
int main()
{
//freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n>>k>>m;
for(i=1;i<=k;i++)
{
cin>>imp[i];
norm[imp[i]]=i;
}
for(i=1;i<=m;i++)
{
cin>>x>>y>>z;
v[x].push_back({y,z});
v[y].push_back({x,z});
}
for(i=1;i<=n;i++)
for(j=1;j<(1<<k);j++)
d[i][j]=1LL*1e17;
for(i=1;i<=k;i++)
{
d[imp[i]][(1<<(i-1))]=0;
}
ans=LLONG_MAX;
dij();
cout<<ans;
return 0;
}
Compilation message (stderr)
cities.cpp: In function 'void dij()':
cities.cpp:57:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<v[x].size(); i++)
~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |