本文共 1000 字，大约阅读时间需要 3 分钟。

单源最短路径

题目链接： /

题目大意

就是求一个有向图中一个点到所有点的最短距离。

思路

最短路模板题，就用 dij 加堆优化即可。

代码

#include
   
    #include
    
     #include
     
      using namespace std;struct node {   	int x, to, nxt;}e[200001];int n, m, s, x, y, z, le[100001], KK;long long dis[100001];bool in[100001];priority_queue 
      
       
        , vector
        
         
           >, greater
          
           
             > > q;void add(int x, int y, int z) { e[++KK] = (node){ z, y, le[x]}; le[x] = KK;}void dij() { //dij加堆优化 memset(dis, 0x7f, sizeof(dis)); dis[s] = 0; q.push(make_pair(0, s)); while (!q.empty()) { int now = q.top().second; long long now_d = q.top().first; q.pop(); if (in[now]) continue; in[now] = 1; for (int i = le[now]; i; i = e[i].nxt) if (!in[e[i].to] && now_d + 1ll * e[i].x < dis[e[i].to]) { dis[e[i].to] = now_d + 1ll * e[i].x; q.push(make_pair(dis[e[i].to], e[i].to)); } }}int main() { scanf("%d %d %d", &n, &m, &s); for (int i = 1; i <= m; i++) { scanf("%d %d %d", &x, &y, &z); add(x, y, z); } dij(); for (int i = 1; i <= n; i++) printf("%lld ", dis[i]); return 0;}