tarjan缩点后求最短路

2024/10/24 算法 c++ 数据结构图论 tarjan 最短路

正则表达式

题目背景

小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$。

输出格式

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

样例输入

样例输出

实现

简述一下题目，存在一有向有环图，在任意强连通块里面的路径权值均可看作0，求1号点到n号点最短路。

在tarjan缩点得到的有向无环图上跑一遍Dijkstra即可得到答案

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int inf32 = 1e9 + 7;
constexpr int inf64 = 1e9 + 7;
const int N=2e5;
struct tree{
    int to;
    int w;
};
vector<tree>e[N];
vector<tree>e_dist[N];
int cnt,idx,num;
int dfn[N],instk[N],low[N];
int belong[N];
stack<int> stk;
vector<int>scc[N];
int dout[N];
typedef pair<int,int> PII;
void tarjan(int u){
    dfn[u]=low[u]=++idx;
    stk.push(u);
    instk[u]=1;
    for(auto V:e[u]){
        int v=V.to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instk[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        cnt++;
        int v;
        do{
            v=stk.top();
            stk.pop();
            instk[v]=0;
            scc[cnt].push_back(v);
            belong[v]=cnt;
        }while(v!=u);
    }
}
int dist[N];
void dijkstra(int u){
    priority_queue<PII,vector<PII>,greater<PII>> q;
    dist[u]=0;
    q.push({0,u});
    while(!q.empty()){
        auto [distance,k]=q.top();
        q.pop();
        for(auto V:e_dist[k]){
            int v=V.to;
            int w=V.w;
            if(dist[v]>distance+w){
                dist[v]=distance+w;
                q.push({dist[v],v});
            }
        }
    }
}
void solve(){
    int n,m;
    cin>>n>>m;
    memset(dist,127,sizeof(dist));
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    for(int i=1;i<=cnt;i++){
        for(auto u:scc[i]){
            for(auto v:e[u]){
                e_dist[i].push_back({belong[v.to],v.w});
            }
        }
    }
    dijkstra(belong[1]);
    cout<<dist[belong[n]]<<endl;
}
    
signed main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

LOADING