常乐集训2

不是很乐。
最短路径和强连通分量。
最短路复健的比较快，在无负情况下基本全世界都是dijk，spfa在构造数据下容易被卡的特点好像成为了被薄纱的原因，可是随机数据嘎嘎快。
最短路主要问题和最小生成树类似，主要集中于对题目本身的分析，如何转换到这两个算法本身，还是要多打题锻炼一下思维，果然复健运动包括这些在里面吗。听起来就像是数学一样。
强连通分量的问题可能算是历史遗留性的问题，今年还是觉得它很抽象，题没打多少，净看了。下面是捋了一阵子的结果，还是有一定的不懂，至于左边的人嘛，他玩的那些很有趣，我闲着没事就看他玩，随时都能看，很惬意

#include
using namespace std;
int n,m,dfn[210000],low[210000],st[210000],co[210000],col,top,num;
int T,next[1100000],last[1100000],to[1100000],cnt[1100000];
int TT,nxt[1100000],lst[1100000],To[1100000],ct[1100000];
int visit[1100000],dis[1100000];
struct node{
    int a,b;
    bool operator < (const node &t) const
    {
        return t.a //小根堆 
    }
};
void add(int x,int y,int z){
    next[++T]=last[x];
    last[x]=T;
    to[T]=y;
    cnt[T]=z;//加边，建初始图 
}
void Add(int x,int y,int z){
    nxt[++TT]=lst[x];
    lst[x]=TT;
    To[TT]=y;//重新加边，建新，无强连通图 
    ct[TT]=z;
}
void Tarjan(int u){
    dfn[u]=low[u]=++num;//深搜遍历序号标记 
    st[++top]=u;//当前点入栈 
    for(int i=last[u];i;i=next[i]){
        int v=to[i];
        if(!dfn[v]){//未被深搜遍历过的点 
            Tarjan(v);//下一位，搜 
            low[u]=min(low[u],low[v]);//?
        }
        else if(!co[v])//?
            low[u]=min(low[u],dfn[v]);//?
    }
    if(low[u]==dfn[u]){
        co[u]=++col;//u为代表的的强连通分量，col为编号？ 
        while(st[top]!=u){//? 
            co[st[top]]=col;//?
            top--;//出栈 
        }
        top--;
    }
}
void dijkstra(){
    priority_queueq;
    node op;
    op.a=0,op.b=co[1];
    dis[co[1]]=0;//所以co存的是所有被缩点后残存的点?
    q.push(op);
    while(!q.empty()){
        int u=q.top().b;
        q.pop();
        for(int i=lst[u];i;i=nxt[i]){
            int v=To[i];
            if(dis[u]+ct[i]>n>>m;
    for(int i=1;i>u>>v>>w;
        add(u,v,w);
    }//加边 
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            Tarjan(i);
        }
    }//缩点 
    for(int i=1;i<=n;i++){
        for(int j=last[i];j;j=next[j]){
            int u=i,v=to[j];
            if(co[u]!=co[v]){//遍历两点不在同强连通分量中时，将两强连通分量连边，由于是以u，v为代表的强连通分量，因此边权等同uv边? 
                Add(co[u],co[v],cnt[j]);
            }
        }
    }
    for(int i=1;i<=col;i++){//由于单点也可为强连通分量，所以搜索完后非强连通点也进入了co，因此col为当前点个数?
        dis[i]=0x3f3f3f3f;
    }
    dijkstra();
    cout<<dis[co[n]];
}