題意

有一張 $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;
}