当前位置：首页 > news >正文

洛谷单源最短路径 Dijkstra算法+优先队列

news 2025/6/6 20:38:57

题目描述

给定一个 n 个点，m 条有向边的带非负权图，请你计算从 s 出发，到每个点的距离。

数据保证你能从 s 出发到任意点。

输入格式

第一行为三个正整数 n,m,s。第二行起 m 行，每行三个非负整数 ui,vi,wi，表示从 ui 到 vi 有一条权值为 wi 的有向边。

输出格式

输出一行 n 个空格分隔的非负整数，表示 s 到每个点的距离。

代码：

#include <bits/stdc++.h>
#define MX 200005
using namespace std;
//Dijkstra算法和优先队列
int n,m,s;
long long dis[MX] = {0};
bool visited[MX] = {0};
struct edge {
   int next,to,weight;
};
edge edge[MX];
int head[MX] = {0};
int cnt;//指针
void addedge(int u,int v,int w) {
   edge[++cnt].to = v;
   edge[cnt].next = head[u];
   edge[cnt].weight = w;
   head[u] = cnt;
}
struct priority {
   long long int dis;
   int id;
   //重载运算符维护最小值
   bool operator <(const priority &x)const{
       return x.dis < dis;
   }
};
priority_queue<priority> q;
int main() {
   cin>>n>>m>>s;
   for(int i = 1; i <= n; i++) {
       dis[i] = 2e9;
   }
   while(m--) {
       int u,v,w;
       cin>>u>>v>>w;
       addedge(u,v,w);
   }
   dis[s] = 0;
   q.push((priority) {0,s});
   int u;
   while(!q.empty()) {
       priority tmp = q.top();
       q.pop();
       u = tmp.id;
       //cout<<u<<endl;
       if(!visited[u]) {
           visited[u] = 1;
           for(int i = head[u]; i != 0; i = edge[i].next) {
               if( dis[edge[i].to] > dis[u] + edge[i].weight) {
                   dis[edge[i].to] = dis[u] + edge[i].weight;
                   int v = edge[i].to;
                   if(!visited[v])
                   {
                       q.push((priority){dis[v],v});
                   }
               }
           }
       }
   }
   for(int i = 1; i <= n; i++) {
       cout<<dis[i]<<" ";
   }
   return 0;
}