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<vector>
#include<queue>
#include<utility>
using namespace std;
#define int long long
struct wi{
vector<int> Q;
long long dp[35];
bool odw=0;
}*w;
int32_t main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int n,k,m,x,y,z;
cin>>n>>k>>m;
w=new wi[n+3];
for(int i=1;i<=n;i++)
for(int j=0;j<=32;j++)
w[i].dp[j]=1e18;
for(int i=0;i<k;i++)
{
int x;
cin>>x;
w[x].dp[1<<i]=0;
}
for(int i=1;i<=m;i++)
{
cin>>x>>y>>z;
w[x].Q.push_back(y);
w[x].Q.push_back(z);
w[y].Q.push_back(x);
w[y].Q.push_back(z);
}
priority_queue<pair<long long,int> > kolejka;
for(int i=1;i<(1<<k);i++)
{
for(int pom=1;pom<i;pom++)
{
if((pom|i)!=i)
continue;
int pom2=i^pom;
if(pom>pom2)
continue;
for(int j=1;j<=n;j++)
w[j].dp[i]=min(w[j].dp[i],w[j].dp[pom]+w[j].dp[pom2]);
}
for(int j=1;j<=n;j++)
w[j].odw=0;
for(int j=1;j<=n;j++)
{
if(w[j].dp[i]==1e18)
continue;
kolejka.emplace(-w[j].dp[i],j);
}
while(!kolejka.empty())
{
pair<long long,int> para=kolejka.top();
kolejka.pop();
if(w[para.second].odw)
continue;
//cout<<i<<": "<<-para.first<<" "<<para.second<<"\n";
w[para.second].odw=1;
for(int j=0;j<w[para.second].Q.size();j+=2)
{
int kto=w[para.second].Q[j];
long long ile=-para.first+w[para.second].Q[j+1];
if(ile<w[kto].dp[i])
{
kolejka.emplace(-ile,kto);
w[kto].dp[i]=ile;
}
}
}
}
long long wynik=1e18;
for(int i=1;i<=n;i++)
wynik=min(wynik,w[i].dp[(1<<k)-1]);
cout<<wynik;
return 0;
}
Compilation message (stderr)
cities.cpp: In function 'int32_t main()':
cities.cpp:66:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int j=0;j<w[para.second].Q.size();j+=2)
| ~^~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |