记录编号	252083	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	正则表达式	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	1.264 s
提交时间	2016-04-19 13:14:41	内存使用	79.57 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 300000+10;

struct edge {
	int to, ne, v;
	edge() {}
	edge(int to_, int ne_, int v_) { to = to_, ne = ne_, v = v_; }
}e[maxn*5];
int head[maxn], tots;

inline void add_edge(int fr, int to, int v) {
	e[++tots] = edge(to, head[fr], v); head[fr] = tots;
}

class stack{
private:
	int s[maxn];
	int top_;
	bool instack[maxn];
public:
	inline int top() { return s[top_]; }
	inline int size() { return top_; }
	inline bool in(int &num) { return instack[num]; }
	inline void pop() {
		instack[s[top_]] = false;
		top_--;
	}
	inline void push(int num) {
		instack[num] = true;
		s[++top_] = num;
	}
};

template <class T> class stack_{
private:
	T s[maxn<<4];
	int top_;
public:
	inline T top() { return s[top_]; }
	inline int size() { return top_; }
	inline void pop() { top_--; }
	inline void push(T num) { s[++top_] = num; }
};

struct info {
	int now, i;
	int statu;
	info() {}
	info(int now_, int i_, int statu_) { now = now_, i = i_, statu = statu_; } 
};

stack s;
stack_ <info> dfs;

int dfn[maxn], low[maxn], tot;
int be[maxn], sccn;

int cnt;

inline void starjan(int beg) {
	dfs.push(info(beg, 0, 1));
	while(dfs.size()) {
		info d = dfs.top(); dfs.pop();
		int now = d.now, i = d.i, statu = d.statu;
		if(statu == 1) {//进入 
			dfn[now] = low[now] = ++cnt;
			s.push(now);
			if(!head[now]) dfs.push(info(now, 0, 4));//没有子节点直接到循环结束 
			else dfs.push(info(now, head[now], 2));//进入前循环 
		} else if(statu == 2) {//前循环 
			int to = e[i].to;
			if(!dfn[to]) {
				dfs.push(info(now, i, 3));//压入后循环 
				dfs.push(info(to, 0, 1));//访问子节点 
			} else if(s.in(to)){
				low[now] = min(low[now], low[to]);//操作 
				if(e[i].ne) dfs.push(info(now, e[i].ne, 2));//下一条边并不会结束 
				else dfs.push(info(now, 0, 4));//下一条边为0，结束到循环结束 
			}
		} else if(statu == 3) {//后循环 
			low[now] = min(low[now], low[e[i].to]);
			if(e[i].ne) dfs.push(info(now, e[i].ne, 2));//访问下一个节点 
			else dfs.push(info(now, 0, 4));
		} else if(statu == 4) {//循环结束 
			if(dfn[now] == low[now]) {
				int tmp;
				sccn++;
				do {
					tmp = s.top(); s.pop();
					be[tmp] = sccn;
				} while(tmp != now);
			}
		}
	}
} 


void tarjan(int now) {
	int to;
	low[now] = dfn[now] = ++tot;
	s.push(now);
	for(int i = head[now]; i; i = e[i].ne) {
		to = e[i].to;
		if(!dfn[to]){
			tarjan(to);
			low[now] = min(low[to], low[now]);
		}else if(s.in(to)){
			low[now] = min(low[to], low[now]);
		}
	}
	if(dfn[now] == low[now]) {
		int tmp;
		sccn++;
		do {
			tmp = s.top();
			s.pop();
			be[tmp] = sccn;
		}while(tmp != now);
	}
} 


inline void handle_edge(int now) {
	for(int i = head[now]; i; i = e[i].ne) {
		int to = e[i].to;
		if(be[now] == be[to]) e[i].v = 0;
	}
}

int n, m;

inline int get_num() {
	int ans = 0;
	int f = 1;
	char tmp = getchar();
	while(tmp < '0' || tmp > '9') { if(tmp == '-') f = -1; tmp = getchar(); }
	while(tmp <= '9' && tmp >= '0') {
		ans = 10*ans + tmp - '0';
		tmp = getchar();
	}
	return f*ans;
}

inline void read() {
	n = get_num();
	m = get_num();
	int a, b, c;
	for(int i = 1; i <= m; i++) {
		a = get_num();
		b = get_num();
		c = get_num();
		add_edge(a, b, c);
	}
}

struct pr {
	int now, dis;
	pr() {}
	pr(int now_, int dis_) { now = now_, dis = dis_; } 
	bool operator < (const pr &b) const{
		return dis == b.dis ? now > b.now : dis > b.dis;
	}
};

int dis[maxn];

inline int dij() {
	memset(dis, 127, sizeof(dis));
	priority_queue<pr> q;
	q.push(pr(1, 0));
	dis[1] = 0;
	int now, ndis;
	while(!q.empty()) {
		now = q.top().now, ndis = q.top().dis;
		q.pop();
		if(ndis > dis[now]) continue;
		for(int i = head[now]; i; i = e[i].ne) {
			int to = e[i].to;
			if(dis[to] > dis[now]+e[i].v) {
				dis[to] = dis[now] + e[i].v;
				q.push(pr(to, dis[to]));
			}
		}
	}
	return dis[n];
}

inline void solve() {
	if(n <= 1e5) {
		for(int i = 1; i <= n; i++) {
			if(!dfn[i]) tarjan(i);
		}
	} else {
		for(int i = 1; i <= n; i++) {
			if(!dfn[i]) starjan(i);
		}
	}
	for(int i = 1; i <= n; i++) {
		handle_edge(i);
	}
	printf("%d", dij());	
}
int main() {
	freopen("regexp.in", "r", stdin);
	freopen("regexp.out", "w", stdout);
	read();
	solve();
	return 0;
}