#堆优化dijkstra#洛谷 1828 jzoj 1287 codevs 2038 ssl 1693 香甜的黄油

本文主要是介绍#堆优化dijkstra#洛谷 1828 jzoj 1287 codevs 2038 ssl 1693 香甜的黄油，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

有$n$个点，求每个点的单源最短路径的最短和

---

分析

其实跑$n$遍$spfa$或$dijkstra$堆优化就行了

---

代码

#include <cstdio>
#include <queue>
struct node{int y,w,next;}e[2901];
int n,m,dis[801][801],ls[801],mark[801];
struct rec{int x,d;bool operator <(const rec &t)const{return d>t.d;}
};
std::priority_queue<rec>q; int ans=1000000;
int in(){int ans=0; char c=getchar();while (c<48||c>57) c=getchar();while (c>47&&c<58) ans=ans*10+c-48,c=getchar();return ans;
}
void print(int ans){if (ans>9) print(ans/10);putchar(ans%10+48);
}
int main(){int k=in(); n=in(); m=in();while (k--) mark[in()]++;for (register int i=1;i<=m;i++){register int x=in(),y=in(),w=in();e[i]=(node){y,w,ls[x]}; ls[x]=i;e[i+m]=(node){x,w,ls[y]}; ls[y]=i+m;}for (register int j=1;j<=n;j++){while (q.size()) q.pop();for (register int i=1;i<=n;i++) dis[j][i]=1000000;dis[j][j]=0; q.push((rec){j,0});while (q.size()){//堆优化register int x=q.top().x,d=q.top().d; q.pop();if (dis[j][x]!=d) continue;//懒惰删除法for (register int i=ls[x];i;i=e[i].next)if (dis[j][x]+e[i].w<dis[j][e[i].y]){//松弛操作dis[j][e[i].y]=dis[j][x]+e[i].w;q.push((rec){e[i].y,dis[j][e[i].y]});}}}for (register int i=1;i<=n;i++){register int sum=0;for (register int j=1;j<=n;j++)sum+=dis[i][j]*mark[j];ans=ans<sum?ans:sum;}return !printf("%d",ans);
}

这篇关于#堆优化dijkstra#洛谷 1828 jzoj 1287 codevs 2038 ssl 1693 香甜的黄油的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---