记录编号	250800	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	正则表达式	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	2.298 s
提交时间	2016-04-15 22:18:43	内存使用	15.81 MiB

#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cstring>
#define N 211110
using namespace std;
ifstream in("regexp.in");
ofstream out("regexp.out");
int n,m;
int INF=(1<<28);
vector<int> F[N],B[N],G[N],C[N];
bool l[N]={0};
vector<int> scc[N];
int dfn[N]={0},low[N]={0};
int color[N]={0};
int col=0,tim=0;
int f[N]={0};
stack<int> S;
void tarjan(int u)
{
	dfn[u]=low[u]=++tim;
	l[u]=1;
	S.push(u);
	int i,v;
	for(i=0;i<G[u].size();i++)
	{
		v=G[u][i];
		if(!dfn[v])
		{
			//out<<u<<' '<<v<<endl;
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(l[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		col++;
		do
		{
			v=S.top();
			S.pop();
			l[v]=0;
			scc[col].push_back(v);
			color[v]=col;
		}while(u!=v);
	}
}
void Dijkstra(int s)
{
	priority_queue <pair<int,int> > q;
	int i,u,v,w;
	memset(l,0,sizeof(l));
	for(i=1;i<=n;i++)f[i]=INF;
	f[s]=0;
	q.push(make_pair(-f[s],s));
	while(!q.empty())
	{
		u=q.top().second;
		q.pop();
		l[u]=0;
		for(i=0;i<F[u].size();i++)
		{
			v=F[u][i];
			w=B[u][i];
			if(f[v]>f[u]+w)
			{
				f[v]=f[u]+w;
				if(!l[v])
				{
					l[v]=1;
					q.push(make_pair(-f[v],v));
				}
			}
		}
	}
}
void SCC()
{
	int i;
	for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	/*for(i=1;i<=n;i++)out<<color[i]<<' ';
	out<<endl;*/
}
void add(int u,int v,int w)
{
	F[u].push_back(v);
	B[u].push_back(w);
}
void rebuild()
{
	int i,j,u,v;
	//map<int,pair<int,int> > F;
	for(i=1;i<=n;i++)
	{
		//u=color[i];
		for(j=0;j<G[i].size();j++)
		{
			v=G[i][j];
			//v=color[G[i][j]];
			//out<<color[i]<<' '<<color[v]<<endl;
			if(color[i]!=color[v])
			{
				add(color[i],color[v],C[i][j]);
			}
		}
	}
}
void read()
{
	int i,u,v,w;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{
		in>>u>>v>>w;
		G[u].push_back(v);
		C[u].push_back(w);
	}
}
void work()
{
	SCC();
	rebuild();
	Dijkstra(color[1]);
	out<<f[color[n]]<<endl;
}
int main()
{
	int __size__ = 20 << 20; // 20MB
	char *__p__ = (char*)malloc(__size__) + __size__;
	__asm__("movl %0, %%esp\n" :: "r"(__p__));
	read();
	work();
	return 0;
}