单源最短路
Dijkstra $O(M • logM)$
无负边权, 单起点多终点, 贪心, 将点分成2种, 黑点已经找到最短路, 白点还没确定
实现步骤:
1. 将起点入优先队列;
2. 从优先队列取出当前离起点最近的节点x, 并标记st[x] = true;
3. 用x松弛x的所有邻接点, 若松弛成功, y入优先队列;
4. 重复2~3知道所有点都标记
void dijkstra(int s)
{
memset(d, 0x3f, sizeof d);
d[s] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, s});
while (heap.size())
{
PII t = heap.top();
heap.pop();
int dist = t.first, v = t.second;
if (!st[v])
{
for (int i = h[v]; ~i; i = ne[i])
{
int j = e[i];
if (d[j] > dist + w[i])
{
d[j] = dist + w[i];
heap.push({d[j], j});
}
}
st[v] = true;
}
}
}
Spfa 最坏时间复杂度 $O(N • M)$
void spfa()
{
memset(d, 0x3f, sizeof d);
d[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (d[j] > d[t] + w[i])
{
d[j] = d[t] + w[i];
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
}
状态:f[i]表示从1到i的最短路方案数.
其实还挺简单的😊
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, M = 4e6 + 10, mod = 100003;
int h[N], e[M], ne[M], idx;
int d[N];
int f[N];
int n, m;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void bfs()
{
memset(d, -1, sizeof d);
d[1] = 0;
f[1] = 1;
queue<int> q;
q.push(1);
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (d[j] == -1)
{
d[j] = d[t] + 1;
f[j] = f[t];
q.push(j);
}
else if (d[j] == d[t] + 1)
f[j] = (f[j] + f[t]) % mod;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
memset(h, -1, sizeof h);
int a, b;
while (m--)
{
cin >> a >> b;
add(a, b);
add(b, a);
}
bfs();
for (int i = 1; i <= n; i++)
cout << f[i] << '\n';
return 0;
}
1. 将k个僵尸城市跑多起点BFS, 标记s步以内的点为危险;
2. 从点1到点n, 有障碍物, 有点权q和p, 求最短路;
温馨提示:
1. 二倍空间
2. 不开long long见祖宗
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
const ll N = 2e5 + 10, M = 4e5 + 10;
ll h[N], e[M], ne[M], idx;
ll c[N], w[N];
ll d[N];
bool st[N], backup[N];
ll n, m, k, s, p, Q;
queue<PLL> q;
void add(ll a, ll b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void bfs()
{
while (q.size())
{
PLL t = q.front();
q.pop();
ll v = t.first, dist = t.second;
w[v] = Q;
if (dist != s)
{
for (ll i = h[v]; ~i; i = ne[i])
{
ll j = e[i];
if (!st[j] && !backup[j])
{
q.push({j, dist + 1});
st[j] = true;
}
}
}
}
}
void dijkstra(ll s)
{
memset(st, 0, sizeof st);
memset(d, 0x3f, sizeof d);
d[s] = 0;
priority_queue<PLL, vector<PLL>, greater<PLL>> heap;
heap.push({0, s});
while (heap.size())
{
PLL t = heap.top();
heap.pop();
ll dist = t.first, v = t.second;
if (!st[v] && !backup[v])
{
for (ll i = h[v]; ~i; i = ne[i])
{
ll j = e[i];
if (d[j] > dist + w[j])
{
d[j] = dist + w[j];
heap.push({d[j], j});
}
}
st[v] = true;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k >> s >> p >> Q;
for (ll i = 2; i < n; i++) w[i] = p;
for (ll i = 1; i <= k; i++)
{
cin >> c[i];
q.push({c[i], 0});
st[c[i]] = backup[c[i]] = true;
}
memset(h, -1, sizeof h);
ll a, b;
while (m--)
{
cin >> a >> b;
add(a, b);
add(b, a);
}
bfs();
w[1] = w[n] = 0;
dijkstra(1);
cout << d[n];
return 0;
}
1. 加边以后, 最短路不可能变大;
2. 那么加边以后的最短路缩小的幅度应该尽可能小;
3. 从点1出发跑最短路得到d1[i]表示1到i的最短路, 同理d2[i]表示i到n的最短路;
4. 若链接x和y两点, 最新的最短路可能是d1[x] + 1 + d2[y] <= d1[y] + d2[y]
5. 为了使缩小的幅度尽量小, d1[y] - d1[x]的差值尽量小, 考虑将s中的点按d1排序;
6. 排序后枚举S中的点i和i+1, 那么就不需要n*n枚举点对.
7. ans = max(ans, min(d1[s[i]] + 1 + d2[s[i + 1], d1[n]));
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, M = 4e5 + 10;
int h[N], e[M], ne[M], idx;
int s[N];
int d1[N], d2[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool cmp(int a, int b)
{
return d1[a] < d1[b];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= k; i++) cin >> s[i];
memset(h, -1, sizeof h);
int a, b;
while (m--)
{
cin >> a >> b;
add(a, b);
add(b, a);
}
queue<int> q;
memset(d1, -1, sizeof d1);
d1[1] = 0;
q.push(1);
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (d1[j] == -1)
{
d1[j] = d1[t] + 1;
q.push(j);
}
}
}
memset(d2, -1, sizeof d2);
d2[n] = 0;
q.push(n);
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (d2[j] == -1)
{
d2[j] = d2[t] + 1;
q.push(j);
}
}
}
sort(s + 1, s + k + 1, cmp);
int res = 0;
for (int i = 1; i < k; i++)
res = max(res, d1[s[i]] + d2[s[i + 1]] + 1);
cout << min(res, d1[n]);
return 0;
}
k很小, 直接一个离散化, floyd就AC了 😃
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 10, M = 810;
ll st[N];
ll s[N];
ll f[M][M];
struct Cow
{
ll a, b, w;
bool operator< (const Cow &u) const
{
return w < u.w;
}
} g[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n, m, K;
cin >> n >> m >> K;
for (ll i = 0; i < m; i++) cin >> g[i].a >> g[i].b >> g[i].w;
sort(g, g + m);
for (ll i = 0; i < K; i++) st[g[i].a] = st[g[i].b] = 1;
for (ll i = 1; i <= n; i++) s[i] = s[i - 1] + st[i];
memset(f, 0x3f, sizeof f);
for (ll i = 0; i < K; i++)
f[s[g[i].a]][s[g[i].b]] = f[s[g[i].b]][s[g[i].a]] = g[i].w;
n = s[n];
for (ll k = 1; k <= n; k++)
for (ll i = 1; i <= n; i++)
for (ll j = 1; j <= n; j++)
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
vector<ll> ans;
for (ll i = 1; i <= n; i++)
for (ll j = 1; j < i; j++) ans.push_back(f[i][j]);
sort(ans.begin(), ans.end());
cout << ans[K - 1];
return 0;
}
