蓝桥杯算法提高VIP-道路和航路 （C++代码）

参考代码:

#include <bits/stdc++.h>
constexpr auto Inf = 0X3F3F3F3F;
typedef long long LL;
using namespace std;

namespace IO {
	inline LL read() {
		LL o = 0, f = 1; char c = getchar();
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
		return o * f;
	}
	inline char recd() {
		char o; while ((o = getchar()) != 'Q' && o != 'A'); return o;
	}
}
using namespace IO;

const int SIZE = 1E5 + 7;

struct EDGES {
	int next, to, w;
} E[SIZE << 6]; int head[SIZE], cnt, T, R, P, S;

inline void Add(int from, int to, int w) {
	E[cnt].to = to, E[cnt].w = w, E[cnt].next = head[from], head[from] = cnt++;
}

int dis[SIZE], inq[SIZE]; deque<int> que;

void SPFA() {
	memset(dis, Inf, sizeof dis); dis[S] = 0, inq[S] = 1; que.push_back(S);
	while (!que.empty()) {
		int now = que.front(); que.pop_front();
		inq[now] = 0;
		for (int pos = head[now]; ~pos; pos = E[pos].next)
			if (dis[E[pos].to] > dis[now] + E[pos].w) {
				dis[E[pos].to] = dis[now] + E[pos].w;
				if (!inq[E[pos].to]) {
					if (que.empty())
						que.push_back(E[pos].to);
					else
						dis[E[pos].to] < dis[que.front()] ? que.push_front(E[pos].to) : que.push_back(E[pos].to);
					inq[E[pos].to] = 1;
				}
			}
	}
}


int main() {
	memset(head, -1, sizeof head);
	T = read(), R = read(), P = read(), S = read();
	for (int pos = 1, from, to, w; pos <= R; pos++)
		from = read(), to = read(), w = read(), Add(from, to, w), Add(to, from, w);
	for (int pos = 1, from, to, w; pos <= P; pos++)
		from = read(), to = read(), w = read(), Add(from, to, w);
	SPFA();
	for (int pos = 1; pos <= T; pos++)
		dis[pos] == Inf ? printf("NO PATH\n") : printf("%d\n", dis[pos]);
}