Loading...

洛谷P2169 正则表达式

check评论:0 条 remove_red_eye浏览量:376 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-09-17

题意简述:

给定一个有向图,如果一些点在同一个强连通分量内,则他们之间边权为0,求出1到n最短距离

思路:直接$tarjan$找出强连通分量后重新建图,从第一个点所在的强连通分量跑一个$spfa$,输出第$n$个点所在强连通分量最短距离即可

#include <bits/stdc++.h>
using namespace std;
int head[200010];
struct edge
{
    int next,to,dis;
}e[1000010];
int low[200010],dfn[200010],vis[200010],dis[200010],na;
int belong[200010],cnt,n,m;
stack<int> st;
void add(int u,int v,int dis)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].dis=dis;
    head[u]=cnt;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++cnt;
    st.push(u);
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!belong[v])
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u])
    {
        na++;
        while(1)
        {
            int v=st.top();
            st.pop();
            belong[v]=na;
            if(v==u)
            {
                break;
            }
        }
    }
}
void spfa(int x)
{
    queue<int> q;
    q.push(x);
    memset(dis,0x3f,sizeof(dis));
    vis[x]=1;
    dis[x]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].dis)
            {
                dis[v]=dis[u]+e[i].dis;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }    
    }
}
int from[1000010],to[1000010],diss[1000010];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        from[i]=u;
        to[i]=v;
        diss[i]=w;
        add(u,v,w);
    }
    cnt=0; 
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
    memset(head,0,sizeof(head));
    memset(e,0,sizeof(e));
    cnt=0;
    for(int i=1;i<=m;i++)
    {
        add(belong[from[i]],belong[to[i]],diss[i]);
    }
    spfa(belong[1]);
    cout<<dis[belong[n]];
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名