P4779 【模板】单源最短路径（标准版）

求单源最短路， 输出距离

Solution

\(nlogn\) 堆优化 \(Djs\)

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

typedef long long LL;

using namespace std;

LL RD(){

    LL out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const LL maxn = 1000019,INF = 0xfffffffffffffff;

LL head[maxn],nume = 1;

struct Node{

    LL v,dis,nxt;

    }E[maxn << 3];

void add(LL u,LL v,LL dis){

    E[++nume].nxt = head[u];

    E[nume].v = v;

    E[nume].dis = dis;

    head[u] = nume;

    }

LL num, nr, s;

bool vis[maxn];

LL d[maxn];

struct node{

	LL u, d;

	bool operator < (const node &a)const{

		return d > a.d;

		}

	};

void Djs(LL s){

	for(LL i = 1;i <= num;i++)d[i] = INF;

	priority_queue<node>Q;

	d[s] = 0;

	Q.push((node){s, d[s]});

	while(!Q.empty()){

		LL u = Q.top().u;Q.pop();

		if(vis[u])continue;

		vis[u] = 1;

		for(LL i = head[u];i;i = E[i].nxt){

			LL v = E[i].v, dis = E[i].dis;

			if(d[u] + dis < d[v]){

				d[v] = d[u] + dis;

				Q.push((node){v, d[v]});

				}

			}

		}

	}

int main(){

	num = RD();nr = RD();s = RD();

	for(int i = 1;i <= nr;i++){

		LL u = RD(), v = RD(), dis = RD();

		add(u, v, dis);

		}

	Djs(s);

	for(int i = 1;i <= num;i++)printf("%lld ", d[i]);

	return 0;

	}