正则表达式(regexp)hgoi0527

正则表达式(regexp)hgoi0527 题解


题目描述

  • 小 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
  • 5 5
    1 2 1
    2 3 6
    3 4 1
    4 2 1
    3 5 2
  • 输出样例1
  • 3
  • 数据规模
  • 对于 40%的数据,1<=n<=1000, 1<=m<=10000
    对于 70%的数据,1<=n<=5000, 1<=m<=100000
    对于 100%的数据,1<=n<=200000, 1<=m<=1000000

题目解析

  • 筛去题目描述50%的废话。
  • 简单说,就是一个变种的最短路问题,同时在每一个强连通分量中所有的边权为0。
  • 所以使用tarjan算法先求出每一个节点所属于的强连通分量,将其处理后再用SPFA求出最短路。
  • 当然我这里最开始考虑出现了失误,忽视了起点处在强连通分量的情况,所以修改后我使用了一边spfa一边处理的办法

最后附上sxn大佬AC程序

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
void ff(){
    freopen("regexp.in","r",stdin);
    freopen("regexp.out","w",stdout);
}
const int MAXN=200020;
struct Edge{
    int from,to,w;
    Edge(int a,int b,int c):from(a),to(b),w(c){}
};
vector <Edge> edge;
vector <int> G[MAXN];
int n,m;
stack <int> S;
int low[MAXN],pre[MAXN];
int sccno[MAXN];
int dfs_lock,scc_cnt;
void dfs(int u){
    pre[u]=low[u]=++dfs_lock;
    S.push(u);
    int siz=G[u].size();
    for (int i=0;i<siz;i++){
        int v=edge[G[u][i]].to;
        if(!pre[v]){
            dfs(v);
            low[u]=min(low[u],low[v]);
        }else if(!sccno[v]){
            low[u]=min(low[u],pre[v]);
        }
    }
    if(low[u]==pre[u]){
        scc_cnt++;
        for (;;){
            int x=S.top();S.pop();
            sccno[x]=scc_cnt;
            if(x==u) break;
        }
    }
}
void find_scc(){
    dfs_lock=scc_cnt=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for (int i=1;i<=n;i++){
        if(!pre[i]){
            dfs(i);
        }
    }
}
queue <int> q;
bool visited[MAXN];
int dist[MAXN];
void spfa(){
    memset(visited,false,sizeof(visited));
    memset(dist,0x7f,sizeof(dist));
    visited[1]=true;
    dist[1]=0;
    q.push(1);
    while (!q.empty()){
        int x=q.front();
        q.pop();
        visited[x]=false;
        int siz=G[x].size();
        for (int i=0;i<siz;i++){
            Edge &e=edge[G[x][i]];
            int v=e.to;
            if(sccno[x]==sccno[v]) e.w=0;
            int w=e.w;
            if(dist[x]+w<dist[v]){
                dist[v]=dist[x]+e.w;
                if(!visited[v]){
                    q.push(v);
                    visited[v]=true;
                }
            }
        }
    }
}
int main(){
    int size = 128 << 20;
    char *p = (char*)malloc(size) + size;
    __asm__("movl %0, %%esp\n" :: "r"(p));
    ff();
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        edge.push_back(Edge(x,y,z));
        G[x].push_back(edge.size()-1);
    }
    find_scc();
    spfa();
    cout<<dist[n];
    return 0;
}


发表评论

电子邮件地址不会被公开。 必填项已用*标注