1、B站视频链接:D02 最短路 Dijkstra 算法_哔哩哔哩_bilibili
题目链接:【模板】单源最短路径(弱化版) - 洛谷
#include
using namespace std;
#define INF 2147483647
int n,m,s,a,b,c;
const int N=100010;
struct edge{int v,w;};//终点和边权
vector
int d[N],vis[N];
void dijkstra(int s){
for(int i=0;i<=n;i++){
d[i]=INF;//初始化所有点到原点距离为无穷大
}
d[s]=0;//到自身距离为0
for(int i=1;i int u=0; for(int j=1;j<=n;j++){//枚举n个点 if(!vis[j]&&d[j] } vis[u]=1;//标记当前距离最短的点出圈 for(auto ed:e[u]){//枚举当前点的所有邻边 int v=ed.v,w=ed.w; if(d[v]>d[u]+w){//三角形松弛操作 d[v]=d[u]+w; } } } } int main(){ cin>>n>>m>>s; for(int i=0;i cin>>a>>b>>c; e[a].push_back({b,c});//a到b边权为c } dijkstra(s); for(int i=1;i<=n;i++){ printf("%d ",d[i]); } return 0; } #include using namespace std; const int N=100010; int n,m,s,a,b,c; struct edge{int v,w;}; vector int d[N],vis[N]; void dijkstra(int s){ memset(d,0x3f,sizeof d);d[s]=0; priority_queue q.push({0,s}); while(q.size()){ auto t=q.top();q.pop(); int u=t.second; if(vis[u])continue;//已经出队的就跳过 vis[u]=1;//出队标记 for(auto ed:e[u]){ int v=ed.v,w=ed.w; if(d[v]>d[u]+w){ d[v]=d[u]+w; q.push({-d[v],v});//加上负号大根堆等价于小根堆 } } } } int main(){ cin>>n>>m>>s; for(int i=0;i cin>>a>>b>>c,e[a].push_back({b,c}); } dijkstra(s); for(int i=1;i<=n;i++)printf("%d ",d[i]); return 0; } 相关链接
发表评论