记录编号	249271	评测结果	AAAAAAAAAAAAAEEEEEEA
题目名称	正则表达式	最终得分	70
用户昵称	asddddd	是否通过	未通过
代码语言	C++	运行时间	2.046 s
提交时间	2016-04-12 14:52:01	内存使用	11.53 MiB

#include<iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <stack>
#include <queue>
#include <vector>
#define maxn 210000
using namespace std;
struct edge{
    int to,cost;
};
vector<edge>Tu[maxn];
vector<edge>G[maxn];
vector<int>suo[maxn];
int DFN=1,prevv[maxn],dist[maxn],last[maxn],ins[maxn],cnt,n,m,mark[maxn];
stack<int>sta;
void addedge(int from,int to,int cost){
    Tu[from].push_back((edge){to,cost});
}
void tarjan(int u){
    prevv[u]=last[u]=++DFN;
    sta.push(u);
    ins[u]=1;
    for (int i=0; i<Tu[u].size(); i++) {
        int v=Tu[u][i].to;
        if (!prevv[v]) {
            tarjan(v);
            last[u]=min(last[u], last[v]);
        }
        else if(ins[v]){
            last[u]=min(last[u], prevv[v]);
        }
    }
    if (prevv[u]==last[u]) {
        cnt++;
        while (1) {
            int k=sta.top();
            ins[k]=0;
            sta.pop();
            suo[cnt].push_back(k);
            mark[k]=cnt;
            if (k==u) {
                break;
            }
        }
    }
}
void SPFA(int s){
    queue<int>que;
    que.push(s);
    bool inq[maxn];
    que.push(s);
    memset(dist, -1, sizeof(dist));
    dist[s]=0;
    memset(inq, 0, sizeof(inq));
    while (!que.empty()) {
        int k=que.front();
        inq[k]=0;
        que.pop();
        for (int i=0; i<G[k].size(); i++) {
            edge &e=G[k][i];
            if (dist[e.to]==-1||dist[e.to]>dist[k]+e.cost) {
                dist[e.to]=dist[k]+e.cost;
                if (!inq[e.to]) {
                    que.push(e.to);
                    inq[e.to]=1;
                }
            }
        }
    }
}
void init(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for (int i=0; i<m;i++) {
        int from,to,cost;
        cin>>from>>to>>cost;
        addedge(from, to, cost);
    }
    for (int i=1; i<=n; i++) {
        if (!prevv[i]) {
            tarjan(i);
        }
    }
    for (int i=1;i<=cnt; i++) {
        for (int j=0; j<suo[i].size(); j++) {
            int t=suo[i][j];
            for (int k=0; k<Tu[t].size(); k++) {
                int to=mark[Tu[t][k].to],cost=Tu[t][k].cost;
                if (to!=i)
                G[i].push_back((edge){to,cost});
            }
        }
    }
}
void work(){
    SPFA(mark[1]);
    cout<<dist[mark[n]];
}
int main(){
    freopen("regexp.in", "r", stdin);
    freopen("regexp.out", "w", stdout);
    init();
    work();
}