美文网首页
正则表达式

正则表达式

作者: 番薯夹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;
}

相关文章

  • Linux命令行与Shell脚本编程大全-shell正则表达式

    本章内容: 定义正则表达式 了解基本正则表达式 扩展正则表达式 创建正则表达式 定义正则表达式 正则表达式是你定义...

  • 正则相关

    正则表达式基本语法 正则表达式常见字符 正则表达式特殊字符 正则表达式数量词 正则表达式边界匹配 正则表达式逻辑或...

  • 正则表达式系列-1

    正则表达式系列-1正则表达式系列-2正则表达式系列-3正则表达式系列-4 什么是正则表达式 正则表达式就是用事先定...

  • 正则表达式

    正则表达式 - 教程正则表达式 - 简介正则表达式 - 语法正则表达式 - 元字符正则表达式 - 运算符优先级正则...

  • Python基础入门 - 正则表达式与综合实战

    1. 初识正则表达式 1.1 介绍 步骤介绍正则表达式入门及应用正则表达式的进阶正则表达式案例 1.2 正则表达式...

  • Java正则表达式参考

    Java正则表达式入门 java正则表达式应用 深入浅出之正则表达式(一) 深入浅出之正则表达式(二) 正则表达式...

  • 正则表达式

    正则表达式 正则表达式就是记录文本规则的代码 正则表达式常用的元字符 正则表达式常用的限定符 正则表达式举例:这里...

  • Python爬虫(十)_正则表达式

    本篇将介绍python正则表达式,更多内容请参考:【python正则表达式】 什么是正则表达式 正则表达式,又称规...

  • python正则表达式

    本篇将介绍python正则表达式,更多内容请参考:【python正则表达式】 什么是正则表达式 正则表达式,又称规...

  • 正则表达式

    了解正则表达式基本语法 能够使用JavaScript的正则对象 正则表达式简介 什么是正则表达式 正则表达式:用于...

网友评论

      本文标题:正则表达式

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