C++(g++ 7.5.0) 解法, 执行用时: 373ms, 内存消耗: 3972K, 提交时间: 2022-08-13 20:20:50

// NC50381 - 道路和航线
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[])
{
	const int INF = 1000000000;
	cin.tie(0)->sync_with_stdio(0);
	int T, R, P, S;
	cin >> T >> R >> P >> S;
	vector<vector<pair<int, int>>> g(T);
	int u, v, w;
	for (int i = 0; i < R; i++) {
		cin >> u >> v >> w;
		g[u - 1].push_back({v - 1, w});
		g[v - 1].push_back({u - 1, w});
	}
	for (int i = 0; i < P; i++) {
		cin >> u >> v >> w;
		g[u - 1].push_back({v - 1, w});
	}
	vector<int> dist(T, INF);
	deque<int> q;
	dist[S - 1] = 0;
	for (q.push_back(S - 1); !q.empty(); ) {
		auto u = q[0];
		q.pop_front();
		for (auto t: g[u]) {
			int v = t.first, w = t.second;
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				if (q.empty() || dist[v] > dist[q.front()])
					q.push_back(v);
				else
					q.push_front(v);
			}
		}
	}
	for (auto x: dist)
		if (x != INF)
			cout << x << "\n";
		else
			cout << "NO PATH\n";
	return 0;
}

C++(clang++11) 解法, 执行用时: 582ms, 内存消耗: 2696K, 提交时间: 2021-02-04 21:19:56

#include<bits/stdc++.h>
using namespace std;
int t,r,p,s,a,b,c,i,e[250001],f[250001],h[25011],w[250001],l[25011],v[25011],k,x,M=0x3f3f3f3f;
deque<int>q;
void g(int a,int b,int c)
{
	e[++k]=b,f[k]=h[a],h[a]=k,w[k]=c;
}int main()
{
	cin>>t>>r>>p>>s;
	q.push_back(s);
	for(;r--;)
	{
		cin>>a>>b>>c;
		g(a,b,c),g(b,a,c);
	}for(;p--;)
	{
		cin>>a>>b>>c;
		g(a,b,c);
	}for(i=1;i<=t;i++)l[i]=M;
	memset(v,0,sizeof v);
	l[s]=0;v[s]=1;
	while(q.size())
	{
		x=q.front();
		q.pop_front();
		v[x]=0;
		for(i=h[x];i;i=f[i])
		{
			if(l[x]+w[i]<l[e[i]])
			{
				l[e[i]]=l[x]+w[i];
				if(!v[e[i]])
				{
					v[e[i]]=1;
					if(q.size()&&l[e[i]]<l[q.front()])q.push_front(e[i]);
					else q.push_back(e[i]);
				}
			}
		}
	}for(i=1;i<=t;i++)
	{
		if(l[i]==M)puts("NO PATH");
		else cout<<l[i]<<'\n';
	}
}