P2169 正则表达式
题目背景
小Z童鞋一日意外的看到小X写了一个正则表达式的高级程序，这个正则表达式程序仅仅由字符“0”,“1”，“.”和“*”构成，但是他能够匹配出所有在OJ上都AC的程序的核心代码！小Z大为颇感好奇，于是他决定入侵小X的电脑上去获得这个正则表达式的高级程序。
题目描述
在 Internet 网络中的每台电脑并不是直接一对一连通的，而是某些电脑之间存在单向的网络连接，也就是说存在 A 到 B 的连接不一定存在 B 到 A 的连接，并且有些连接传输速度很快，有些则很慢，所以不同连接传输所花的时间是有大有小的。另外，如果存在 A 到 B 的连接的同时也存在 B 到 A 的连接的话，那么 A 和 B 实际上处于同一局域网内，可以通过本地传输，这样花费的传输时间为 0。
现在小 Z 告诉你整个网络的构成情况，他希望知道从他的电脑（编号为 1），到小 X 的电脑（编号为 n）所需要的最短传输时间。
输入格式
第一行两个整数 n,m，表示有 n 台电脑，m 个连接关系。
接下来 m 行，每行三个整数 u,v,w，表示从电脑 u 到电脑 v 传输信息的时间为 w。
输出格式
输出文件仅一行为最短传输时间。
输入输出样例
输入 #1
3 2 1 2 1 2 3 1
输出 #1
2
输入 #2
5 5 1 2 1 2 3 6 3 4 1 4 2 1 3 5 2
输出 #2
3
说明/提示
- 对于 40% 的数据，1≤n≤1e3, 1≤m≤1e4；
- 对于 70% 的数据，1≤n≤5×1e3， 1≤m≤1e5；
- 对于 100% 的数据，1≤n≤2×1e5， 1≤m≤1e6。
Tarjan缩点 + dijkstra
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<tuple>
#define inf 9187201950435737471
#define int long long
#define endl '\n'
#define F first
#define S second
using namespace std;
typedef pair<int, int> pii;const int N = 10086, mod = 998244353;int n, m;
int w[N];
vector<pii> e[N];
int dfn[N], low[N], ti;
stack<int> st;
bool inst[N];
int id[N], cnt;
vector<pii> ee[N];
int dis[N];
priority_queue<pii, vector<pii>, greater<pii> > q;
bool v[N];void tarjan(int u) {dfn[u] = low[u] = ++ti;st.push(u), inst[u] = true;for (auto x : e[u]) {int j = x.F;if (!dfn[j]) {tarjan(j);low[u] = min(low[u], low[j]);} else if (inst[j]) low[u] = min(low[u], dfn[j]);}if (low[u] == dfn[u]) {int y;cnt++;do {y = st.top();st.pop();inst[y] = false;id[y] = cnt;} while (u != y);}}int dij() {memset(dis, 127, sizeof dis);dis[id[1]] = 0;q.push({0, id[1]});while (q.size()) {auto [d, u] = q.top();q.pop();if (v[u]) continue;v[u] = true;for (auto x : ee[u]) {int j = x.F, w = x.S;if (dis[j] > dis[u] + w) {dis[j] = dis[u] + w;q.push({dis[j], j});}}}return dis[id[n]];
}void solve() {cin >> n >> m;for (int i = 1; i <= m; i++) {int a, b, c;cin >> a >> b >> c;e[a].push_back({b, c});}for (int i = 1; i <= n; i++) {if (!dfn[i]) tarjan(i);}for (int u = 1; u <= n; u++) {for (auto i : e[u]) {int j = i.F, c = i.S;int a = id[u], b = id[j];if (a != b) ee[a].push_back({b, c});}}cout << dij();
}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int T = 1;
// cin >> T;while (T--) solve();return 0;
}