本文主要是介绍Tarjan+最短路计数，CF567E. President and Roads，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
Problem - 567E - Codeforces
二、解题报告
1、思路分析
警钟敲烂——注意求最短路的时候是单向边
题意就是一个有向图，然后s到t的最短路一定存在，问
1、我们走最短路的所有情况中有没有一定经过的。
2、对于不是最短路上的边或者不是一定经过的边，我们在最多减少其边权到1的情况下，能不能使其变成一定经过的边，如果能，要减少多少？
对于1、，我们求出所有最短路径，在新图上找桥，桥就是一定会走的边，这个用tarjan求就行
对于2、，我们枚举所有不是桥的边，如果dst(s, u) + w(u, v) + dst(v, t) - (dst(s, t) - 1) < w，那么我们就可以将其减少得到一条长度为dst(s, t) - 1的更短路使其变成一定经过的边
思路还是比较简单，还是注意求最短路的时候是单向边qaq
2、复杂度
时间复杂度： O(n + m + nlogm)空间复杂度：O(n + m)
3、代码详解
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;#define FIN freopen("in.txt", "r", stdin);
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define mkp make_pair
#define int long longconst int N = 1e5 + 10, M = 1e5 + 10;
typedef pair<int, int> PII;
int n, m, s, t;
int head[N], idx, dsts[N], dstt[N];
int dfn[N], low[N], tot;
bool vis[M << 1], bri[M << 1], st[M << 1];
struct edge
{int v, w, nxt;
} edges[M << 1];void addedge(int u, int v, int w)
{edges[idx] = {v, w, head[u]}, head[u] = idx++;
}void add(int u, int v, int w)
{addedge(u, v, w), addedge(v, u, w);
}void tarjan(int u, int pre)
{dfn[u] = low[u] = ++tot;for (int i = head[u]; ~i; i = edges[i].nxt){if (!st[i])continue;int v = edges[i].v;if (!dfn[v]){tarjan(v, i);low[u] = min(low[u], low[v]);if (low[v] > dfn[u])bri[i] = bri[i ^ 1] = true;}else if (i != (pre ^ 1)){low[u] = min(low[u], dfn[v]);}}
}signed main()
{FIOmemset(head, -1, sizeof head);cin >> n >> m >> s >> t;for (int i = 0, a, b, c; i < m; i++){cin >> a >> b >> c;add(a, b, c);}memset(dsts, 0x3f, sizeof dsts), memset(dstt, 0x3f, sizeof dstt);// shortest pathpriority_queue<PII, vector<PII>, greater<PII>> pq;pq.emplace(mkp(dsts[s] = 0, s));while (pq.size()){auto [d, u] = pq.top();pq.pop();if (vis[u])continue;vis[u] = 1;for (int i = head[u]; ~i; i = edges[i].nxt){if (i & 1)continue;int v = edges[i].v, w = edges[i].w;if (vis[v])continue;if (dsts[u] + w < dsts[v])pq.emplace(mkp(dsts[v] = dsts[u] + w, v));}}memset(vis, 0, sizeof vis);pq.emplace(mkp(dstt[t] = 0, t));while (pq.size()){auto [d, u] = pq.top();pq.pop();if (vis[u])continue;vis[u] = 1;for (int i = head[u]; ~i; i = edges[i].nxt){if (i % 2 == 0)continue;int v = edges[i].v, w = edges[i].w;if (vis[v])continue;if (dstt[u] + w < dstt[v])pq.emplace(mkp(dstt[v] = dstt[u] + w, v));}}for (int i = 0, mi = dsts[t]; i < idx; i += 2){int u = edges[i ^ 1].v, v = edges[i].v, w = edges[i].w;int d = dsts[u] + dstt[v] + w;if (d == mi)st[i] = st[i ^ 1] = 1;}// tarjantarjan(s, -1);for (int i = 0, mi = dsts[t]; i < idx; i += 2){int u = edges[i ^ 1].v, v = edges[i].v, w = edges[i].w;int d = dsts[u] + dstt[v] + w;if (bri[i]){cout << "YES\n";}else{if (d - mi + 1 < w){cout << "CAN " << d - mi + 1 << '\n';}elsecout << "NO\n";}}return 0;
}这篇关于Tarjan+最短路计数，CF567E. President and Roads的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
