美文网首页
正则表达式

正则表达式

作者: 番薯夹islandfsj | 来源:发表于2018-09-28 20:50 被阅读0次
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    
    using namespace std;
    
    int n,m,u,v,w,s,t=0,tot=0,top=0;
    int dfn[50001],low[50001],stack[50001],scc[50001];
    int heap[50001],dijkstra[50001];
    int head[50001],to[200001],data[200001],value[200001];
    bool vis[50001];
    
    void tarjan(int now){
        int next;
        dfn[now]=low[now]=++t;
        stack[++top]=now;
        vis[now]=true;
        next=head[now];
        while (next!=0){
            if (dfn[data[next]]==0){
                tarjan(data[next]);
                low[now]=min(low[now],low[data[next]]);
            }
            else
                if (vis[data[next]])
                    low[now]=min(low[now],dfn[data[next]]);
            next=to[next];
        }
        if (dfn[now]==low[now]){
            while (stack[top]!=now){
                vis[stack[top]]=false;
                scc[stack[top]]=now;
                top--;
            }
            vis[stack[top]]=false;
            scc[stack[top]]=now;
            top--;
        }
    }
    
    void adjust(int now){
        int next=now,minNum=dijkstra[heap[now]];
        if (now*2-1<=s && dijkstra[heap[now*2-1]]<minNum){
            next=now*2-1;
            minNum=dijkstra[heap[now*2-1]];
        }
        if (now*2<=s && dijkstra[heap[now*2]]<minNum){
            next=now*2;
            minNum=dijkstra[heap[now*2]];
        }
        if (now!=next){
            heap[0]=heap[now];
            heap[now]=heap[next];
            heap[next]=heap[0];
            adjust(next);
        }
    }
    
    int main(){
        freopen("regexp.in","r",stdin);
        freopen("regexp.out","w",stdout);
        int i,j,now,next;
        bool judge;
        scanf("%d%d",&n,&m);
        for (i=1;i<=m;i++){
            scanf("%d%d%d",&u,&v,&w);
            judge=false;
            next=head[u];
            while (next!=0){
                if (data[next]==v){
                    judge=true;
                    value[next]=min(value[next],w);
                    break;
                }
                next=to[next];
            }
            if (!judge){
                tot++;
                to[tot]=head[u];
                data[tot]=v;
                value[tot]=w;
                head[u]=tot;
            }
        }
        
        memset(vis,false,sizeof(vis));
        for (i=1;i<=n;i++)
            if (dfn[i]==0)
                tarjan(i);
                
        for (i=1;i<=n;i++)
            heap[i]=i;
        memset(dijkstra,63,sizeof(dijkstra));
        dijkstra[1]=0;
        s=n;
        for (i=1;i<=n;i++){
            now=heap[1];
            heap[0]=heap[1];
            heap[1]=heap[s];
            heap[s]=heap[0];
            s--;
            next=head[now];
            while (next!=0){
                if (scc[now]==scc[data[next]])
                    value[next]=0;
                dijkstra[data[next]]=min(dijkstra[data[next]],dijkstra[now]+value[next]);
                next=to[next];
            }
            for (j=s/2;j>=1;j--)
                adjust(j);
        }
        printf("%d\n",dijkstra[n]);
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:正则表达式

          本文链接:https://www.haomeiwen.com/subject/umkmoftx.html