dijkstra + tarjan 93pts

#include <bits/stdc++.h>
using namespace std;

const int kMaxN = 200000 + 5;
const int kMaxM = 1000000 + 5;

int n, m;

struct Edge {
	int from;
	int to;
	int nxt;
	long long w;
} tmpe[kMaxM], e[kMaxM];
int tot, head[kMaxN];
void Add(int x, int y, long long w) {
	e[++tot] = (Edge){x, y, head[x], w};
	head[x] = tot;
}

struct Node {
	int x;
	long long d;
	bool operator < (const Node A) const {
		return d > A.d;
	}
};
priority_queue<Node> q;

int dfn[kMaxN], low[kMaxN];
bool vis1[kMaxN];
int col[kMaxN];
stack<int> st;
int cnt;
void Tarjan(int x) {
	st.push(x);
	dfn[x] = low[x] = ++cnt;
	vis1[x] = 1;
	for (int i = head[x]; i != 0; i = e[i].nxt) {
		int to = e[i].to;
		if (!dfn[to]) {
			Tarjan(to);
			low[x] = min(low[x], low[to]);
		}
		else if (vis1[to] != 0) {
			low[x] = min(low[x], low[to]);
		}
	}
	if (low[x] == dfn[x]) {
		int now = 0;
		while (st.top() != x) {
			now = st.top();
			vis1[now] = 0;
			col[now] = x;
			st.pop();
		}
		col[x] = x;
		st.pop();
	}
}

long long dis[kMaxN];
bool vis2[kMaxN];
void Dijkstra(int s) {
	memset(vis2, 0, sizeof(vis2));
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	q.push((Node){s, 0});
	while (!q.empty()) {
		int now = q.top().x;
		q.pop();
		if (vis2[now] == 1) {
			continue;
		}
		vis2[now] = 1;
		for (int i = head[now]; i != 0; i = e[i].nxt) {
			int to = e[i].to;
			if (col[now] == col[to]) {
				dis[to] = dis[now];
				q.push((Node){to, dis[to]});
				continue;
			}
			if (dis[to] > dis[now] + e[i].w) {
				dis[to] = dis[now] + e[i].w;
				q.push((Node){to, dis[to]});
			}
		}
	}
} 

int main() {
	
//	freopen("regexp.in", "r", stdin);
//	freopen("regexp.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int x, y, w;
		scanf("%d%d%d", &x, &y, &w);
		Add(x, y, w);
	}
	for (int i = 1; i <= n; i++) {
		if (dfn[i] == 0) {
			Tarjan(i);
		}
	}
	Dijkstra(1);
	cout << dis[n];
	return 0;
} 
/*
3 2
1 2 1
2 3 1
*/
/*
5 5
1 2 1
2 3 6
3 4 1
4 2 1
3 5 2
*/

记录