【算法提高——第三讲(一)】图论(1)

#include<bits/stdc++.h>
using namespace std;
const int N=2510,M=6210,INF=1e9;
int n,m,s,ed;
int h[N],e[2*M],w[2*M],ne[2*M],idx;
int dis[N];
bool st[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int spfa(int s)
{
    fill(dis,dis+N,INF);
    dis[s]=0;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>dis[t]+w[i])
            {
                dis[j]=dis[t]+w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return dis[ed];
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m>>s>>ed;
    fill(h,h+N,-1);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    cout<<spfa(s);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=410,INF=1e9;
int n,m;
int h[N],e[M],w[M],ne[M],idx;
int dis[N];
bool st[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void spfa(int s)
{
    fill(dis,dis+N,INF);
    dis[s]=0;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>dis[t]+w[i])
            {
                dis[j]=dis[t]+w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
}
int main()
{
    fill(h,h+N,-1);
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    spfa(1);
    int _max=-INF;
    for(int i=1;i<=n;i++)
    {
        if(dis[i]==INF)
        {
            cout<<-1<<endl;
            return 0;
        }
        if(_max<dis[i])
        {
            _max=dis[i];
        }
    }
    cout<<_max<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=810,M=2910,INF=1e9;
int n,p,C;
int h[N],e[M],w[M],ne[M],idx;
int dis[N];
bool st[N];
int cows[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void spfa(int s)
{
    fill(dis,dis+N,INF);
    dis[s]=0;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>dis[t]+w[i])
            {
                dis[j]=dis[t]+w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
}
int main()
{
    fill(h,h+N,-1);
    cin>>n>>p>>C;
    for(int i=0;i<n;i++)
    {
        cin>>cows[i];
    }
    for(int i=0;i<C;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    int ans=INF;
    for(int i=1;i<=p;i++)
    {
        spfa(i);
        int sum=0;
        for(int j=0;j<n;j++)
        {
            if(dis[cows[j]]==INF)
            {
                sum=INF;
                break;
            }
            else
            {
                sum+=dis[cows[j]];
            }
        }
        ans=min(ans,sum);
    }
    cout<<ans<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=2010,M=200010,INF=1e9;
int n,m,A,B;
int h[N],e[M],ne[M],idx;
double w[M];
bool st[N];
double dis[N];
void add(int a,int b,double c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
double spfa(int s)
{
    dis[s]=1;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dis[j]<dis[t]*w[i])
            {
                dis[j]=dis[t]*w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return dis[B];
}
int main()
{
    fill(h,h+N,-1);
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        double c;
        cin>>a>>b>>c;
        c=(100-c)/100;
        add(a,b,c),add(b,a,c);
    }
    cin>>A>>B;
    printf("%.8f",100/spfa(A));
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=510,INF=1e9;
int m,n;
int g[N][N];
int dis[N];
int stop[N];
void bfs()
{
    fill(dis,dis+N,INF);
    queue<int> q;
    dis[1]=0;
    q.push(1);
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        for(int i=1;i<=n;i++)
        {
            if(g[t][i]&&dis[i]>dis[t]+1)
            {
                dis[i]=dis[t]+1;
                q.push(i);
            }
        }
    }
}
int main()
{
    cin>>m>>n;
    getchar();
    string line;
    while(m--)
    {
        getline(cin,line);
        int cnt=0,p;
        stringstream ssin(line);
        while(ssin>>p) stop[cnt++]=p;
        for(int i=0;i<cnt;i++)
        {
            for(int j=i+1;j<cnt;j++)
            {
                g[stop[i]][stop[j]]=1;
            }
        }
    }
    bfs();
    if(dis[n]==INF) cout<<"NO";
    else cout<<dis[n]-1;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=110,INF=1e9;
int m,n;
int g[N][N];
int d[N];
int w[N],L[N];
bool st[N];
vector<PII> node[N];
int spfa(int left,int right)
{
    fill(d,d+N,INF);
    d[0]=0;
    queue<int> q;
    for(int i=0;i<=n;i++)
    {
        q.push(i);
        st[i]=true;
    }
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=0;i<=n;i++)
        {
            if(g[t][i]!=INF)
            {
                if(L[i]>=left&&L[i]<=right&&d[i]>d[t]+g[t][i])
                {
                    d[i]=d[t]+g[t][i];
                    if(!st[i])
                    {
                        q.push(i);
                        st[i]=true;
                    }
                }
            }
        }
    }
    return d[1];
}
int main()
{
    fill(g[0],g[0]+N*N,INF);
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        int p,l,x;
        cin>>p>>l>>x;
        w[i]=p;
        L[i]=l;
        for(int j=0;j<x;j++)
        {
            int t,v;
            cin>>t>>v;
            node[i].push_back(make_pair(t,v));
        }
    }
    for(int i=1;i<=n;i++)
    {
        g[i][i]=0;
        for(int j=0;j<node[i].size();j++)
        {
            int t=node[i][j].first,v=node[i][j].second;
            if(abs(L[i]-L[t])<=m)
            {
                g[t][i]=min(g[t][i],v);
            }
        }
    }
    for(int i=1;i<=n;i++) g[0][i]=w[i];
    int ans=INF;
    for(int i=L[1]-m;i<=L[1];i++)
    {
        ans=min(ans,spfa(i,i+m));
    }
    cout<<ans;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=50010,M=200010,INF=1e9;
int n,m;
int h[N],e[M],w[M],ne[M],idx;
bool st[N];
int dis[6][N];
int source[6];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void djk(int s,int dis[])
{
    fill(dis,dis+N,INF);
    fill(st,st+N,false);
    dis[s]=0;
    priority_queue<PII,vector<PII>,greater<PII> >heap;
    heap.push(make_pair(0,s));
    while(heap.size())
    {
        PII t=heap.top();
        heap.pop();
        int ver=t.second,distance=t.first;
        if(st[ver]) continue;
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>dis[ver]+w[i])
            {
                dis[j]=dis[ver]+w[i];
                heap.push(make_pair(dis[j],j));
            }
        }
    }
}
int dfs(int u,int start,int distance)
{
    if(u>5) return distance;
    int res=INF;
    for(int i=1;i<=5;i++)
    {
        if(!st[i])
        {
            int next=source[i];
            st[i]=true;
            res=min(res,dfs(u+1,i,distance+dis[start][next]));
            st[i]=false;
        }
    }
    return res;
}
int main()
{
    fill(h,h+N,-1);
    cin>>n>>m;
    for(int i=1;i<=5;i++) cin>>source[i];
    source[0]=1;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    fill(st,st+N,false);
    for(int i=0;i<6;i++) djk(source[i],dis[i]);
    cout<<dfs(1,0,0);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=20010,INF=1e9;
int n,m,K;
int h[N],e[M],w[M],ne[M],idx;
int dis[N];
bool st[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool check(int bound)
{
    fill(dis,dis+N,INF);
    fill(st,st+N,false);
    dis[1]=0;
    deque<int> q;
    q.push_back(1);
    while(!q.empty())
    {
        int t=q.front();
        q.pop_front();
        if(st[t])
            continue;
        st[t]=true;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i],v=w[i]>bound;
            if(dis[j]>dis[t]+v)
            {
                dis[j]=dis[t]+v;
                if(!v)
                {
                    q.push_front(j);
                }
                else
                {
                    q.push_back(j);
                }
            }
        }
    }
    return dis[n]<=K;
}
int main()
{
    fill(h,h+N,-1);
    cin>>n>>m>>K;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    int l=0,r=1e6+1;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    if(r==1e6+1) r=-1;
    cout<<r<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=25010,M=1500010,INF=1e9;
int h[N],e[M],w[M],ne[M],idx;
int n,r,p,s;
int dis[N];
bool st[N];
int id[N];
vector<int> block[N];   //连通块编号
int bcnt;   //连通块个数
queue<int> q;   //拓扑排序队列
int din[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int bid)
{
    id[u]=bid;
    block[bid].push_back(u);
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!id[j]) dfs(j,bid);
    }
}
void djk(int bid)
{
    priority_queue<PII,vector<PII>,greater<PII> > heap;
    for(int i=0;i<block[bid].size();i++)
    {
        int ver=block[bid][i];
        heap.push(make_pair(dis[ver],ver));
    }
    while(heap.size())
    {
        PII t=heap.top();
        heap.pop();
        int ver=t.second,distance=t.first;
        if(st[ver]) continue;
        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>dis[ver]+w[i])
            {
                dis[j]=dis[ver]+w[i];
                if(id[j]==id[ver]) heap.push(make_pair(dis[j],j));
            }
            if(id[j]!=id[ver]&&--din[id[j]]==0) q.push(id[j]);
        }
    }
}
void topsort()
{
    fill(dis,dis+N,INF);
    dis[s]=0;
    for(int i=1;i<=bcnt;i++)
    {
        if(!din[i])
        {
            q.push(i);
        }
    }
    while(q.size())
    {
        int t=q.front();
        q.pop();
        djk(t);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    fill(h,h+N,-1);
    cin>>n>>r>>p>>s;
    for(int i=0;i<r;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    for(int i=1;i<=n;i++)
    {
        if(!id[i])
        {
            bcnt++;
            dfs(i,bcnt);
        }
    }
    for(int i=0;i<p;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        din[id[b]]++;
        add(a,b,c);
    }
    topsort();
    for(int i=1;i<=n;i++)
    {
        if(dis[i]>=INF/2) cout<<"NO PATH"<<endl;
        else cout<<dis[i]<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=2000010,INF=1e9;
int n,m;
int w[N];
int hs[N],ht[N],e[M],ne[M],idx;
int dmin[N],dmax[N];
int q[N];
bool st[N];
void add(int h[],int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void spfa(int h[],int dis[],int type)
{
    queue<int> q;
    if(type==0)
    {
        fill(dis,dis+N,INF);
        dis[1]=w[1];
        q.push(1);
    }
    else
    {
        fill(dis,dis+N,-INF);
        dis[n]=w[n];
        q.push(n);
    }
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(type==0&&dis[j]>min(dis[t],w[j])||type==1&&dis[j]<max(dis[t],w[j]))
            {
                if(type==0)
                {
                    dis[j]=min(dis[t],w[j]);
                }
                else
                {
                    dis[j]=max(dis[t],w[j]);
                }
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    fill(hs,hs+N,-1);
    fill(ht,ht+N,-1);
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(hs,a,b),add(ht,b,a);
        if(c==2) add(hs,b,a),add(ht,a,b);
    }
    spfa(hs,dmin,0);
    spfa(ht,dmax,1);
    int res=0;
    for(int i=1;i<=n;i++)
    {
        res=max(res,dmax[i]-dmin[i]);
    }
    cout<<res;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1010,M=40010,INF=1e9;
int n,m;
int ed;
int h[N],w[M],e[M],ne[M],idx;
int dis[N];
bool st[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int djk(int s)
{
    fill(dis,dis+N,INF);
    fill(st,st+N,false);
    dis[s]=0;
    priority_queue<PII,vector<PII>,greater<PII> > heap;
    heap.push(make_pair(0,s));
    while(heap.size())
    {
        PII t=heap.top();
        heap.pop();
        int ver=t.second;
        if(st[ver]) continue;
        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>dis[ver]+w[i])
            {
                dis[j]=dis[ver]+w[i];
                heap.push(make_pair(dis[j],j));
            }
        }
    }
    return dis[ed];
}
int main()
{
    while(cin>>n>>m>>ed)
    {
        fill(h,h+N,-1);
        for(int i=0;i<m;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(b,a,c);
        }
        djk(ed);
        int num,start;
        cin>>num;
        int ans=INF;
        for(int i=0;i<num;i++)
        {
            cin>>start;
            ans=min(ans,dis[start]);
        }
        if(ans!=INF) cout<<ans<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=11,M=400,P=1<<10,INF=1e9;
int n,m,p,k;
int h[N*N],e[M],w[M],ne[M],idx;
int g[N][N],key[N*N];
int dis[N*N][P];
bool st[N*N][P];
set<PII> edges;
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void build()
{
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int u=0;u<4;u++)
            {
                int x=i+dx[u],y=j+dy[u];
                if(!x||x>n||!y||y>m) continue;
                int a=g[i][j],b=g[x][y];
                if(!edges.count(make_pair(a,b))) add(a,b,0);
            }
        }
    }
}
int bfs()
{
    //memset(dis,0x3f,sizeof dis);
    fill(dis[0],dis[0]+N*N*P,INF);
    dis[1][0]=0;
    deque<PII> q;
    q.push_back(make_pair(1,0));
    while(q.size())
    {
        PII t=q.front();
        q.pop_front();
        if(st[t.first][t.second]) continue;
        st[t.first][t.second]=true;
        if(t.first==n*m) return dis[t.first][t.second];
        if(key[t.first])
        {
            int state=t.second|key[t.first];
            if(dis[t.first][state]>dis[t.first][t.second])
            {
                dis[t.first][state]=dis[t.first][t.second];
                q.push_front(make_pair(t.first,state));
            }
        }
        for(int i=h[t.first];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(w[i]&&!(t.second>>w[i]-1&1)) continue;
            if(dis[j][t.second]>dis[t.first][t.second]+1)
            {
                dis[j][t.second]=dis[t.first][t.second]+1;
                q.push_back(make_pair(j,t.second));
            }
        }
    }
    return -1;
}
int main()
{
    cin>>n>>m>>p>>k;
    for(int i=1,t=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            g[i][j]=t++;
        }
    }
    fill(h,h+N*N,-1);
    for(int i=0;i<k;i++)
    {
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        int a=g[x1][y1],b=g[x2][y2];
        edges.insert(make_pair(a,b)),edges.insert(make_pair(b,a));
        if(c) add(a,b,c),add(b,a,c);
    }
    build();
    int num;
    cin>>num;
    for(int i=0;i<num;i++)
    {
        int x,y,id;
        cin>>x>>y>>id;
        key[g[x][y]]|=1<<id-1;
    }
    cout<<bfs()<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=400010,mod=100003;
int n,m;
int h[N],e[M],ne[M],idx;
int dis[N],cnt[N];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs()
{
    memset(dis,0x3f,sizeof dis);
    dis[1]=0,cnt[1]=1;
    queue<int> q;
    q.push(1);
    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>dis[t]+1)
            {
                dis[j]=dis[t]+1;
                cnt[j]=cnt[t];
                q.push(j);
            }
            else if(dis[j]==dis[t]+1)
            {
                cnt[j]=(cnt[j]+cnt[t])%mod;
            }
        }
    }
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    bfs();
    for(int i=1;i<=n;i++)
    {
        cout<<cnt[i]<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=10010;
struct Ver{
    int ver,type,dist;
    bool operator > (const Ver &w) const
    {
        return dist>w.dist;
    }
    Ver(int _ver,int _type,int _dist)
    {
        ver=_ver,type=_type,dist=_dist;
    }
};
int n,m;
int S,T;
int h[N],e[M],w[M],ne[M],idx;
int dis[N][2],cnt[N][2];
bool st[N][2];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int djk()
{
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);
    memset(dis,0x3f,sizeof dis);
    dis[S][0]=0,cnt[S][0]=1;
    priority_queue<Ver,vector<Ver>,greater<Ver> > heap;
    heap.push(Ver(S,0,0));
    while(heap.size())
    {
        Ver t=heap.top();
        heap.pop();
        int ver=t.ver,type=t.type,distance=t.dist,_count=cnt[ver][type];
        if(st[ver][type]) continue;
        st[ver][type]=true;
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dis[j][0]>distance+w[i])
            {
                dis[j][1]=dis[j][0],cnt[j][1]=cnt[j][0];
                heap.push(Ver(j,1,dis[j][1]));
                dis[j][0]=distance+w[i],cnt[j][0]=_count;
                heap.push(Ver(j,0,dis[j][0]));
            }
            else if(dis[j][0]==distance+w[i])
            {
                cnt[j][0]+=_count;
            }
            else if(dis[j][1]>distance+w[i])
            {
                dis[j][1]=distance+w[i],cnt[j][1]=_count;
                heap.push(Ver(j,1,dis[j][1]));
            }
            else if(dis[j][1]==distance+w[i])
            {
                cnt[j][1]+=_count;
            }
        }
    }
    int res=cnt[T][0];
    if(dis[T][0]+1==dis[T][1]) res+=cnt[T][1];
    return res;
}
int main()
{
    int cases;
    cin>>cases;
    while(cases--)
    {
        cin>>n>>m;
        memset(h,-1,sizeof h);
        idx=0;
        for(int i=0;i<m;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
        }
        cin>>S>>T;
        cout<<djk()<<endl;
    }
    return 0;
}