洛谷 P3008 [USACO11JAN] Roads and Planes G

题意

有一张 $n$ 点 $(m_1+m_2)$ 边的无向图，其中 $m_1$ 条为无向边，另外 $m_2$ 条为有向边， 无向边的边权可以为负。求 $s$ 到其他每个点的最短路。

思路

使用 SPFA 会 T 掉一两个点，但由于数据水，加个 SLF 优化就能过。
SLF 优化：把普通队列换成双端队列，然后每次插入时和队头比较，如果更优插到队头否则插队尾。

代码

// Problem: P3008 [USACO11JAN] Roads and Planes G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3008
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
#define int long long
const int INF = 1e18;
using PII = pair<int, int>;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int n, m1, m2, s;
	cin >> n >> m1 >> m2 >> s;
	s--;
	
	vector<vector<PII>> G(n);
	for(int i = 0, u, v, w; i < m1; i++){
		cin >> u >> v >> w;
		u--, v--;
		G[u].emplace_back(v, w);
		G[v].emplace_back(u, w);
	}
	for(int i = 0, u, v, w; i < m2; i++){
		cin >> u >> v >> w;
		u--, v--;
		G[u].emplace_back(v, w);
	}
	
	vector<int> dis(n, INF);
	vector<bool> vis(n, false);
	
	auto spfa = [&](int s){
		deque<int> q;
		
		dis[s] = 0;
		vis[s] = true;
		q.push_front(s);
		
		while(q.size()){
			int u = q.front();
			q.pop_front();
			vis[u] = false;
			
			for(auto &edge: G[u]){
				int v = edge.first, w = edge.second;
				if(dis[v] > dis[u] + w){
					dis[v] = dis[u] + w;
					if(!vis[v]){
						vis[v] = true;
						if(q.size() && dis[v] >= dis[q.front()]) q.push_back(v);
						else q.push_front(v);
					}
				}
			}
		}
	};
	spfa(s);
	for(auto &x: dis){
		if(x == INF) cout << "NO PATH" << endl;
		else cout << x << endl;
	}
	return 0;
}