记录编号	250958	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	正则表达式	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	1.719 s
提交时间	2016-04-16 16:01:55	内存使用	5.08 MiB

//KZNS
#include <fstream>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
//
ifstream fin ("regexp.in");
ofstream fout ("regexp.out");
typedef pair<int, int> pr;
const int Nmax = 200003;
const int Mmax = 1000003;
//
int N, M;
vector<pr> gp[Nmax];
int dtm[Nmax] = {0};
int mtm[Nmax] = {0};
int ttmm = 1;
stack<int> tju;
int ed[Nmax];
bool lsd[Nmax] = {0};
queue<int> ls;
//
void fir() {
	fin >> N >> M;
	int a, b, c;
	for (int i = 0; i < M; i++) {
		fin >> a >> b >> c;
		gp[a].push_back(make_pair(b, c));
	}
}
void tj(int x) {
	dtm[x] = mtm[x] = ttmm++;
	tju.push(x);
	for (int i = 0; i < gp[x].size(); i++) {
		if (!dtm[gp[x][i].first])
			tj(gp[x][i].first);
		mtm[x] = min(mtm[x], mtm[gp[x][i].first]);
	}
	if (dtm[x] == mtm[x]) {
		int u;
		while (x != tju.top()) {
			u = tju.top();
			tju.pop();
			mtm[u] = x;
		}
		tju.pop();
	}
}
void SPFA() {
	for (int i = 2; i <= N; i++)
		ed[i] = 0x7fffffff;
	ed[1] = 0;
	ls.push(1);
	lsd[1] = true;
	int u, k;
	while (!ls.empty()) {
		u = ls.front();
		ls.pop();
		lsd[u] = false;
		for (int i = 0; i < gp[u].size(); i++) {
			k = gp[u][i].first;
			if (mtm[u] == mtm[k]) {
				if (ed[u] < ed[k]) {
					ed[k] = ed[u];
					if (!lsd[k]) {
						lsd[k] = true;
						ls.push(k);
					}
				}
			}
			else {
				if (ed[u] + gp[u][i].second < ed[k]) {
					ed[k] = ed[u] + gp[u][i].second;
					if (!lsd[k]) {
						lsd[k] = true;
						ls.push(k);
					}
				}
			}
		}
	}
}
//
int main() {
	int __size__ = 20 << 20;
	char *__p__ = (char*)malloc(__size__) + __size__;
	__asm__("movl %0, %%esp\n" :: "r"(__p__));
	fir();
	tj(1);
	SPFA();
	fout << ed[N] << endl;
	return 0;
}
//UBWH