洛谷 P2169 正则表达式

题目链接https://www.luogu.org/problem/show?pid=2169
题目背景

小Z童鞋一日意外的看到小X写了一个正则表达式的高级程序,这个正则表达式程序仅仅由字符“0”,“1”,“.”和“*”构成,但是他能够匹配出所有在OJ上都AC的程序的核心代码!小Z大为颇感好奇,于是他决定入侵小X的电脑上去获得这个正则表达式的高级程序。

题目描述

在Internet网络中的每台电脑并不是直接一对一连通的,而是某些电脑之间存在单向的网络连接,也就是说存在A到B的连接不一定存在B到A的连接,并且有些连接传输速度很快,有些则很慢,所以不同连接传输所花的时间是有大有小的。另外,如果存在A到B的连接的同时也存在B到A的连接的话,那么A和B实际上处于同一局域网内,可以通过本地传输,这样花费的传输时间为0。

现在小Z告诉你整个网络的构成情况,他希望知道从他的电脑(编号为1),到小X的电脑(编号为n)所需要的最短传输时间。

输入输出格式

输入格式:
第一行两个整数n, m, 表示有n台电脑,m个连接关系。

接下来m行,每行三个整数u,v,w;表示从电脑u到电脑v传输信息的时间为w。

输出格式:
输出文件仅一行为最短传输时间。

输入输出样例

输入样例#1:
3 2
1 2 1
2 3 1
输出样例#1:
2
输入样例#2:
5 5
1 2 1
2 3 6
3 4 1
4 2 1
3 5 2
输出样例#2:
3
说明

对于40%的数据,1<=n<=1000, 1<=m<=10000

对于70%的数据,1<=n<=5000, 1<=m<=100000

对于100%的数据,1<=n<=200000, 1<=m<=1000000

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#define ll long long 
using namespace std;
int head[120005],nex[2000005],to[2000005],v[2000005];
int dfn[120005],low[120005],stac[120005],vis[120005],bel[120005],re[120005];
int n,x,y,ty,topp,tot,tott,cnt,ans,m;
int dfs_clock;
int head2[120005],nex2[2000005],to2[2000005],val[2000005];
inline void add(int x,int y,int z){
    ++tot;
    nex[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
    v[tot]=z;
}
void tarjan(int u){
    vis[u]=true;
    dfn[u]=low[u]=dfs_clock++;
    stac[++topp]=u;
    for(int i=head[u];i;i=nex[i]){
        int dmf=to[i];
        if(!dfn[dmf]){
            tarjan(dmf);
            low[u]=min(low[u],low[dmf]);
        }
        else if(vis[dmf]){
            low[u]=min(low[u],dfn[dmf]);
        }
    }
    if(low[u]==dfn[u]){
        ++cnt;
        bel[u]=cnt;
        vis[u]=false;
        while(stac[topp]!=u){
            bel[stac[topp]]=cnt;
            vis[stac[topp]]=false;
            --topp;
        }topp--;
    }
}
inline void add2(int x,int y,int z){
    ++tott;
    nex2[tott]=head2[x];
    head2[x]=tott;
    to2[tott]=y;
    val[tott]=z;
}
inline void rebuild(){
    for(int i=1;i<=n;i++){
        for(int j=head[i];j;j=nex[j]){
            if(bel[to[j]]!=bel[i]){
                add2(bel[i],bel[to[j]],v[j]);
            }
        }
    }
}
int dis[1000005];
bool vv[1000005];
inline void spfa(){
    memset(dis,0x7f7f,sizeof(dis));
    queue<int> q;
    q.push(bel[1]);
    vv[bel[1]]=true;
    dis[bel[1]]=0;
    while(!q.empty()){
        int dmf=q.front();
        vv[dmf]=0;
        q.pop();
        for(int i=head2[dmf];i;i=nex2[i]){
            int hxr=to2[i];
            if(dis[hxr]>dis[dmf]+val[i]){
                dis[hxr]=dis[dmf]+val[i];
                if(!vv[hxr]){
                    q.push(hxr);
                    vv[hxr]=1;
                }
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); 
    rebuild();
    spfa();
    printf("%d",dis[bel[n]]);
    return 0;
}

裸题,没啥说的

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议