这边建议堆优化,效果更好,还好写
by cout_jerry @ 2023-12-23 22:45:24
这边建议这么写
```cpp
int n,p,c;
vector<pair<int,int>>a[150001];
int f[150001];
int t[150001];
int num[150001];
int dik(int x)
{
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
q.push(make_pair(0ll,x));
while(q.size()>0)
{
int u=q.top().second;
q.pop();
if(t[u]==1)continue;
t[u]=1;
for(int i=0;i<a[u].size();i++)
{
int uu=a[u][i].second;
int vv=a[u][i].first;
if(f[uu]>f[u]+vv)
{
f[uu]=f[u]+vv;
q.push(mp(f[uu],uu));
}
}
}
return 0;
}
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin>>n>>p>>c;
int x,y,z;
for(int i=1;i<=n;i++)
{
cin>>x;
num[x]++;
}
memset(f,0x3f,sizeof f);
f[1]=0;
for(int i=1;i<=c;i++)
{
cin>>x>>y>>z;
a[y].push_back({z,x});
a[x].push_back({z,y});
}
int ans=11451410962;
for(int i=1;i<=p;i++)
{
memset(t,0,sizeof t);
memset(f,0x3f,sizeof f);
f[i]=0;
dik(i);
int s=0;
for(int j=1;j<=p;j++)
{
s+=num[j]*f[j];
}
ans=min(ans,s);
}
cout<<ans;
return 0;
exit(0);
}
```
更好理解
by cout_jerry @ 2023-12-23 22:52:52