洛谷 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;
}