头像

lisx05




离线:21小时前


活动打卡代码 AcWing 347. 野餐规划

lisx05
22小时前
//删边做法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
const int N=35,INF=0x3f3f3f3f;
int n,m,s,g[N][N],tree[N][N],d[N],conn[N],ans,deg;
bool v[N];
void read()
{
    map<string,int> h;
    h["Park"]=1;
    n=1;
    scanf("%d",&m);
    memset(g,0x3f,sizeof g);
    while(m--)
    {
        int x,y,z;
        char sx[12],sy[12];
        scanf("%s%s%d",sx,sy,&z);
        if(!h[sx]) h[sx]=++n;
        if(!h[sy]) h[sy]=++n;
        x=h[sx],y=h[sy];
        g[x][y]=g[y][x]=min(g[x][y],z);
    }
    scanf("%d",&s);
}
void prim()
{
    memset(d,0x3f,sizeof d);
    d[1]=0;
    for(int i=1;i<n;i++)
    {
        int x=0;
        for(int j=1;j<=n;j++)
            if(!v[j]&&(x==0||d[x]>d[j])) x=j;
        v[x]=1;
        for(int y=1;y<=n;y++)
            if(!v[y]&&d[y]>g[x][y])
            {
                d[y]=g[x][y];
                conn[y]=x;
            }
    }
    memset(tree,0x3f,sizeof tree);
    for(int i=2;i<=n;i++)
    {
        ans+=d[i];
        tree[i][conn[i]]=tree[conn[i]][i]=d[i];
        if(conn[i]==1) deg++;
    }
}
void dfs(int x)
{
    v[x]=1;
    for(int y=1;y<=n;y++)
        if(!v[y]&&tree[x][y]<INF) dfs(y);
}
int find_min(int &x,int &y)
{
    int min_edge=1<<30;
    for(int i=2;i<=n;i++)//1号点不考虑 
        if(v[i])
            for(int j=2;j<=n;j++)
                if(!v[j])
                    if(g[i][j]<min_edge)
                        min_edge=g[i][j],x=i,y=j;
    return min_edge;
    //若两个连通块间在原图中没有边,则返回值为INF(因为g的初值就是INF) 
}
void solve()
{
    int min_val=1<<30,mini,minx,miny;
    for(int i=2;i<=n;i++)
    {
        if(tree[1][i]==INF) continue;
        memset(v,0,sizeof v);
        v[1]=1;//找除1外的连通块,v[1]设为1,强制不用1 
        dfs(i);//找删去1后形成的连通块
        int x,y;
        int add_edge=find_min(x,y);
        if(add_edge<INF&&add_edge-tree[1][i]<min_val)
        {
            min_val=add_edge-tree[1][i];
            mini=i,minx=x,miny=y;
        }
    }
    ans+=min_val;
    tree[1][mini]=INF;
    tree[minx][miny]=tree[miny][minx]=g[minx][miny];
}
int main()
{
    read();
    prim();
    while(deg>s)
    {
        solve();
        deg--;
    }
    printf("Total miles driven: %d",ans);
    return 0;
}
/*
思路一:先求一棵最小生成树,
然后只要与1号点相连的边数大于s,就删一条与1相连的边,就形成了两个连通块, 
再连一条边把这两个连通块连起来,
使得新连的这条边的边权-删去的边的边权最小。 
*/
//O(n^4)
//加边做法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
const int N=35,INF=0x3f3f3f3f;
int n,m,s,g[N][N],tree[N][N],d[N],conn[N],ans,deg;
bool v[N],c[N]; 
int f[N],fx[N],fy[N],ver[N],p; 
void read()
{
    map<string,int> h;
    h["Park"]=1;
    n=1;
    scanf("%d",&m);
    memset(g,0x3f,sizeof g);
    while(m--)
    {
        int x,y,z;
        char sx[12],sy[12];
        scanf("%s%s%d",sx,sy,&z);
        if(!h[sx]) h[sx]=++n;
        if(!h[sy]) h[sy]=++n;
        x=h[sx],y=h[sy];
        g[x][y]=g[y][x]=min(g[x][y],z);
    }
    scanf("%d",&s);
}
void prim(int root)
{
    d[root]=0;
    for(int i=1;i<=p;i++)
    {
        int x=0;
        for(int j=1;j<=p;j++)
            if(!v[ver[j]]&&(x==0||d[x]>d[ver[j]])) x=ver[j];
        v[x]=1;
        for(int j=1;j<=p;j++)
        {
            int y=ver[j];
            if(!v[y]&&d[y]>g[x][y])
            {
                d[y]=g[x][y];
                conn[y]=x;
            }
        }   
    }
    //建连通块内的最小生成树,将连通块内到1号点距离最近的点与1号点相连 
    int closest=root;
    for(int i=1;i<=p;i++)
    {
        int x=ver[i];
        if(x==root) continue;
        ans+=d[x];
        tree[x][conn[x]]=tree[conn[x]][x]=d[x];
        if(g[1][x]<g[1][closest]) closest=x;
    }
    deg++;
    ans+=g[1][closest];
    tree[1][closest]=tree[closest][1]=g[1][closest];
}
void dfs(int x)
{
    ver[++p]=x;//ver中存连通块中的所有点 
    c[x]=1;
    for(int y=1;y<=n;y++)
        if(!c[y]&&g[x][y]<INF) dfs(y);
}
void prim_for_all_comp()
{
    memset(d,0x3f,sizeof d);
    memset(c,0,sizeof c);
    memset(tree,0x3f,sizeof tree);
    c[1]=1;//找连通块,不考虑1号点 
    for(int i=2;i<=n;i++)
        if(!c[i])
        {
            p=0;
            dfs(i);
            prim(i);
        }
}
void dp(int x)
{//树形DP求出每个点i到根节点的路径上权值最大的边(fx[i],fy[i]),权值为f[i] 
    v[x]=1;
    for(int y=2;y<=n;y++)
    {
        if(tree[x][y]==INF||v[y]) continue;
        if(f[x]>tree[x][y])
        {
            f[y]=f[x];
            fx[y]=fx[x];
            fy[y]=fy[x];
        }
        else
        {
            f[y]=tree[x][y];
            fx[y]=x;
            fy[y]=y;
        }
        dp(y);
    }
}
bool solve()
{
    int min_val=1<<30,mini;
    for(int i=2;i<=n;i++)//看加哪一条非树边(1,i) 
    {
        if(tree[1][i]!=INF||g[1][i]==INF) continue;
        if(g[1][i]-f[i]<min_val)
            min_val=g[1][i]-f[i],mini=i;
    }
    if(min_val>=0) return false;//无论如何也不可能使答案变得更小了
    ans+=min_val;
    tree[1][mini]=tree[mini][1]=g[1][mini];
    tree[fx[mini]][fy[mini]]=tree[fy[mini]][fx[mini]]=INF;
    //更新以mini为根的子树的f值 
    memset(v,0,sizeof v);
    v[1]=1;//不能更新1号点 
    f[mini]=g[1][mini];
    fx[mini]=1;
    fy[mini]=mini;
    dp(mini);
    return true;
}
int main()
{
    read();
    prim_for_all_comp();
    memset(v,0,sizeof v);
    dp(1);
    while(deg<s)//只要度数小于s,就尝试加一条边把答案变小 
    {
        if(!solve()) break;
        deg++;
    }
    printf("Total miles driven: %d",ans);
    return 0;
}
/*
思路二:(书上的做法)
先找到去掉1号点后的T个连通块,每个连通块内部求最小生成树
若T>s,则无解
把每个连通块和1号点连起来,此时1号点的度数可能小于s,
考虑再连1号点到其他点的边,同时删去一条连边后形成的环上的边,
使得边权和尽量变小。 
*/
//O(n^2)


活动打卡代码 AcWing 346. 走廊泼水节

lisx05
1天前
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=6010;
int T,n,f[N],s[N],ans;
struct tree{
    int x,y,z;
}edge[N];
bool operator <(const tree& a,const tree& b)
{
    return a.z<b.z;
}
int getf(int x)
{
    return f[x]==x?x:f[x]=getf(f[x]);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        ans=0;
        scanf("%d",&n);
        for(int i=1;i<n;i++)
            scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
        sort(edge+1,edge+n);
        for(int i=1;i<=n;i++) f[i]=i,s[i]=1;
        for(int i=1;i<n;i++)
        {
            int x=getf(edge[i].x),y=getf(edge[i].y);
            if(x!=y)
            {
                ans+=(edge[i].z+1)*(s[x]*s[y]-1);
                f[y]=x;
                s[x]+=s[y];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}


活动打卡代码 AcWing 345. 牛站

lisx05
10天前

Bellman_Ford

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=205;
int a[N],b[N],len[N],vals[N],f[N],d[N],n,t,s,e,cnt;
int main()
{
    scanf("%d%d%d%d",&n,&t,&s,&e);
    vals[++cnt]=s;
    vals[++cnt]=e;
    for(int i=1;i<=t;i++)
    {
        scanf("%d%d%d",&len[i],&a[i],&b[i]);
        vals[++cnt]=a[i];
        vals[++cnt]=b[i];
    }
    sort(vals+1,vals+cnt+1);
    cnt=unique(vals+1,vals+cnt+1)-vals-1;
    s=lower_bound(vals+1,vals+cnt+1,s)-vals;
    e=lower_bound(vals+1,vals+cnt+1,e)-vals;
    for(int i=1;i<=t;i++)
    {
        a[i]=lower_bound(vals+1,vals+cnt+1,a[i])-vals;
        b[i]=lower_bound(vals+1,vals+cnt+1,b[i])-vals;
    }
    memset(d,0x3f,sizeof d);
    d[s]=0;
    for(int i=1;i<=n;i++)//Bellman_ford 
    {
        memset(f,0x3f,sizeof f);
        for(int j=1;j<=t;j++)
        {
            if(f[a[j]]>d[b[j]]+len[j]) f[a[j]]=d[b[j]]+len[j];
            if(f[b[j]]>d[a[j]]+len[j]) f[b[j]]=d[a[j]]+len[j];
        }
        memcpy(d,f,sizeof f);
    }
    printf("%d",f[e]);
    return 0;
}

倍增

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=205;
int a[N],b[N],len[N],vals[N],f[25][N][N],d[N],g[N],n,t,s,e,cnt;
//f[i][x][y]表示从x到y恰好走2^i条边的最短路 
int main()
{
    scanf("%d%d%d%d",&n,&t,&s,&e);
    vals[++cnt]=s;
    vals[++cnt]=e;
    for(int i=1;i<=t;i++)
    {
        scanf("%d%d%d",&len[i],&a[i],&b[i]);
        vals[++cnt]=a[i];
        vals[++cnt]=b[i];
    }
    sort(vals+1,vals+cnt+1);
    cnt=unique(vals+1,vals+cnt+1)-vals-1;
    s=lower_bound(vals+1,vals+cnt+1,s)-vals;
    e=lower_bound(vals+1,vals+cnt+1,e)-vals;
    memset(f,0x3f,sizeof f);
    //f[0][][]表示的是经过一条边的最短路,所以f[0][i][i]不能赋为0 
    int L=log2(n);
    for(int i=1;i<=t;i++)
    {
        a[i]=lower_bound(vals+1,vals+cnt+1,a[i])-vals;
        b[i]=lower_bound(vals+1,vals+cnt+1,b[i])-vals;
        if(f[0][a[i]][b[i]]>len[i]) 
            f[0][a[i]][b[i]]=f[0][b[i]][a[i]]=len[i];
    }
    //倍增预处理 
    for(int i=1;i<=L;i++)
        for(int x=1;x<=cnt;x++)
            for(int y=1;y<=cnt;y++)
                for(int z=1;z<=cnt;z++)
                    if(f[i][x][y]>f[i-1][x][z]+f[i-1][z][y])
                        f[i][x][y]=f[i-1][x][z]+f[i-1][z][y];
    //拼凑 
    memset(g,0x3f,sizeof g);
    g[s]=0;
    for(int c=0;c<=L;c++)
        if((n>>c)&1)
        {
            memset(d,0x3f,sizeof d);
            for(int i=1;i<=cnt;i++)
                for(int j=1;j<=cnt;j++)
                    if(d[i]>g[j]+f[c][j][i])
                        d[i]=g[j]+f[c][j][i];
            memcpy(g,d,sizeof d);
        }
    printf("%d",d[e]);
    return 0;
}

矩阵乘法

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=205;
int a[N],b[N],len[N],vals[N],d[N][N],ans[N][N],n,t,s,e,cnt;
void mul(int a[N][N],int b[N][N])//关于min和+的广义矩阵乘法 
{
    int c[N][N];
    memset(c,0x3f,sizeof c);
    for(int i=1;i<=cnt;i++)
        for(int j=1;j<=cnt;j++)
            for(int k=1;k<=cnt;k++)
                c[i][j]=min(c[i][j],a[i][k]+b[k][j]);
    memcpy(a,c,sizeof c);//不能sizeof(a),因为a是指针 
}
int main()
{
    scanf("%d%d%d%d",&n,&t,&s,&e);
    vals[++cnt]=s;
    vals[++cnt]=e;
    for(int i=1;i<=t;i++)
    {
        scanf("%d%d%d",&len[i],&a[i],&b[i]);
        vals[++cnt]=a[i];
        vals[++cnt]=b[i];
    }
    sort(vals+1,vals+cnt+1);
    cnt=unique(vals+1,vals+cnt+1)-vals-1;
    s=lower_bound(vals+1,vals+cnt+1,s)-vals;
    e=lower_bound(vals+1,vals+cnt+1,e)-vals;
    memset(d,0x3f,sizeof d);//经过一条边的最短路,d[i][i]不能赋为0 
    for(int i=1;i<=t;i++)
    {
        a[i]=lower_bound(vals+1,vals+cnt+1,a[i])-vals;
        b[i]=lower_bound(vals+1,vals+cnt+1,b[i])-vals;
        d[a[i]][b[i]]=d[b[i]][a[i]]=min(d[a[i]][b[i]],len[i]);
    }
    memset(ans,0x3f,sizeof ans);
    ans[s][s]=0;//经过0条边的最短路 
    while(n)
    {
        if(n&1) mul(ans,d);
        mul(d,d);
        n>>=1;
    }
    printf("%d",ans[s][e]);
    return 0;
}


活动打卡代码 AcWing 344. 观光之旅

lisx05
11天前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N=110;
int pos[N][N],d[N][N],a[N][N],n,m;
vector<int> path;
void get_path(int i,int j)//找i,j之间的路径,i和j已加入答案序列 
{
    if(pos[i][j]==0) return;//说明i,j之间无中转点,直接相连,返回即可
    get_path(i,pos[i][j]);
    path.push_back(pos[i][j]);
    get_path(pos[i][j],j);
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(d,0x3f,sizeof d);
    for(int i=1;i<=n;i++) d[i][i]=0;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        d[x][y]=d[y][x]=min(d[x][y],z);
    }
    memcpy(a,d,sizeof d);
    int ans=0x3f3f3f3f;
    for(int k=1;k<=n;k++)
    {
        //更新答案 
        for(int i=1;i<k;i++)
            for(int j=i+1;j<k;j++)
                if(ans>(long long)d[i][j]+a[i][k]+a[k][j])
                //极端情况下d[i][j],a[i][k],a[k][j]可能都是无穷大 
                {
                    ans=d[i][j]+a[i][k]+a[k][j];
                    path.clear();
                    path.push_back(i);
                    get_path(i,j);
                    path.push_back(j);
                    path.push_back(k);
                }
        //更新最短路 
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(d[i][j]>d[i][k]+d[k][j])
                {
                    d[i][j]=d[i][k]+d[k][j];
                    pos[i][j]=k;
                }
    }
    if(ans==0x3f3f3f3f)
        printf("No solution.");
    else
        for(int i=0;i<path.size();i++)
            printf("%d ",path[i]);
    return 0; 
}


活动打卡代码 AcWing 343. 排序

lisx05
11天前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=30;
bool d[N][N];
int n,m;
pair<int,int> ans[N];
int floyd()
{
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                d[i][j]|=d[i][k]&d[k][j];
    int flag=1;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            if(d[i][j]==d[j][i]&&d[i][j]==1&&i!=j) return -1;
            if(i!=j&&d[i][j]==0&&d[j][i]==0) flag=0;
        }
    return flag;
}
int main()
{
    while(scanf("%d%d",&n,&m),n)
    {
        memset(d,0,sizeof d);
        bool flag=1;
        for(int t=1;t<=m;t++)
        {
            char str[5];
            scanf("%s",str);
            d[str[0]-'A'][str[2]-'A']=1;
            if(flag)
            {
                int now=floyd();
                if(now==-1)
                {
                    printf("Inconsistency found after %d relations.\n",t);
                    flag=0;
                }
                else if(now==1)
                {
                    printf("Sorted sequence determined after %d relations: ",t);
                    memset(ans,0,sizeof ans);
                    for(int i=0;i<n;i++) ans[i].second=i;
                    for(int i=0;i<n;i++)
                        for(int j=0;j<n;j++)
                            if(d[j][i]&&j!=i) ans[i].first++;
                    sort(ans,ans+n);
                    for(int i=0;i<n;i++)
                    {
                        char c=ans[i].second+'A';
                        cout<<c;
                    }
                    printf(".\n");
                    flag=0;
                }
            }
        }
        if(flag) printf("Sorted sequence cannot be determined.\n");
    }
    return 0;
}


活动打卡代码 AcWing 342. 道路与航线

lisx05
14天前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int N=25010,M=150010;
int h[N],e[M],ne[M],w[M],mark[M],idx;
int n,m,p,s,d[N];
bool v[N];
vector<int> a[N];//每块中的点
int c[N],cnt;
int deg[N];
priority_queue<pair<int,int> > heap;
queue<int> q; 
void add(int a,int b,int c,int k)//k==0双向,k==1单向 
{
    e[++idx]=b;
    w[idx]=c;
    mark[idx]=k;
    ne[idx]=h[a];
    h[a]=idx;
}
void dfs(int x)//找连通块并编号 
{
    c[x]=cnt;
    a[cnt].push_back(x);
    for(int i=h[x];i;i=ne[i])
    {
        if(mark[i]==1) continue;//只看双向边 
        int y=e[i];
        if(!c[y]) dfs(y);
    }
}
void dijkstra(int k)
{
    for(int j=0;j<a[k].size();j++)
        heap.push(make_pair(-d[a[k][j]],a[k][j]));
    while(!heap.empty())
    {
        int x=heap.top().second;
        heap.pop();
        if(v[x]) continue;
        v[x]=1;
        for(int i=h[x];i;i=ne[i])
        {
            int y=e[i];
            if(mark[i]==0)//块内部dijkstra 
            {
                if(d[y]>d[x]+w[i])
                {
                    d[y]=d[x]+w[i];
                    heap.push(make_pair(-d[y],y));
                }
            }
            else//不同块之间先不入堆,拓扑排序 
            {
                d[y]=min(d[y],d[x]+w[i]);
                if(--deg[c[y]]==0) q.push(c[y]);
            }
        }
    }
}
int main()
{
    cin>>n>>m>>p>>s;
    while(m--)//双向边 
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z,0);
        add(y,x,z,0);   
    }
    while(p--)//单向边 
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z,1);
    }
    //找连通块并编号 
    for(int i=1;i<=n;i++)
        if(!c[i])
        {
            cnt++;
            dfs(i);
        }
    //统计每块的总入度 
    for(int x=1;x<=n;x++)
        for(int i=h[x];i;i=ne[i])
        {
            if(mark[i]==0) continue;//只看单向边 
            deg[c[e[i]]]++;
        }
    //对块拓扑排序 
    for(int i=1;i<=cnt;i++)
        if(!deg[i]) q.push(i);
    memset(d,0x3f,sizeof d);
    d[s]=0;
    while(!q.empty())
    {
        int k=q.front();
        q.pop();
        dijkstra(k);
    }
    for(int i=1;i<=n;i++)
        if(d[i]>n*10000) printf("NO PATH\n");
        else printf("%d\n",d[i]);
    return 0;
}


活动打卡代码 AcWing 341. 最优贸易

lisx05
14天前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=100010,M=1000010;
int h[N],e[M],ne[M],w[M],idx;
int n,m,a[N],d[N],f[N];
bool v[N];
queue<int> q;
void add(int a,int b,int c)
{
    e[++idx]=b;
    w[idx]=c;//1只能正向,-1只能反向,2正反都行 
    ne[idx]=h[a];
    h[a]=idx;
}
void spfa(int *d,int st,int t)//因为d是指针,所以要在函数外初始化 
{
    d[st]=a[st];//起点的前缀min或后缀max都是本身的权值 
    q.push(st);
    v[st]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        v[x]=0;
        for(int i=h[x];i;i=ne[i])
        {
            int y=e[i],z=w[i];
            if(z==t||z==2)//当前边能走 
            {
                //若t=1,则是求前缀min;若t=-1,则是求后缀max 
                int val= t==1?min(d[x],a[y]):max(d[x],a[y]);
                if(t==1&&d[y]>val||t==-1&&d[y]<val)
                {
                    d[y]=val;
                    if(!v[y])
                    {
                        q.push(y);
                        v[y]=1;
                    }
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z==1?-1:z);
    }
    memset(d,0x3f,sizeof d);
    spfa(d,1,1);//d数组,从1开始求前缀min,只有1或2的边能走 
    memset(f,0xcf,sizeof f);
    spfa(f,n,-1);//f数组,从n开始求后缀max,只有-1或2的边能走
    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,f[i]-d[i]);
    printf("%d",ans);
    return 0; 
}


活动打卡代码 AcWing 340. 通信线路

lisx05
15天前
//分层图最短路
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int N=1010,M=20010;
int h[N],e[M],w[M],ne[M],idx;
int n,m,k,d[N][N];//d[x][j]表示从1走到x,其中j条边免费(即第j层) 
bool v[N][N];
typedef pair<int,pair<int,int> > PIP;
priority_queue<PIP,vector<PIP>,greater<PIP> > q;
void add(int a,int b,int c)
{
    e[++idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    memset(d,0x3f,sizeof d);
    d[1][0]=0;
    q.push(make_pair(0,make_pair(1,0)));
    while(!q.empty())
    {
        int x=q.top().second.first,j=q.top().second.second;
        q.pop();
        if(v[x][j]) continue;
        v[x][j]=1;
        for(int i=h[x];i;i=ne[i])
        {
            int y=e[i],z=w[i];
            if(d[y][j]>max(d[x][j],z))//走到本层 
            {
                d[y][j]=max(d[x][j],z);
                q.push(make_pair(d[y][j],make_pair(y,j)));
            }
            if(j<k&&d[y][j+1]>d[x][j])//走到下一层(j+1层),此时当前边免费 
            {
                d[y][j+1]=d[x][j];
                q.push(make_pair(d[y][j+1],make_pair(y,j+1)));
            }
        }
    }
    int ans=0x3f3f3f3f;
    for(int j=0;j<=k;j++) ans=min(ans,d[n][j]);
    if(ans==0x3f3f3f3f) printf("-1");
    else printf("%d",ans);
    return 0;
}
//二分答案,双端队列BFS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1010,M=20010;
int h[N],e[M],ne[M],w[M],idx;
int n,m,k,d[N];
deque<int> q;
void add(int a,int b,int c)
{
    e[++idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx;
}
bool check(int t)
{
    memset(d,0x3f,sizeof d);
    d[1]=0;
    q.push_back(1);
    while(!q.empty())
    {
        int x=q.front();
        q.pop_front();
        for(int i=h[x];i;i=ne[i])
        {
            int y=e[i],z=w[i]>t?1:0;
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                if(z==0) q.push_front(y);
                else q.push_back(y);
            }
        }
    }
    return d[n]<=k;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    int L=0,R=1000001;
    while(L<R)
    {
        int mid=(L+R)>>1;
        if(check(mid)) R=mid;
        else L=mid+1;
    }
    if(L==1000001) printf("-1");
    else printf("%d",L);
    return 0;
}


活动打卡代码 AcWing 851. spfa求最短路

lisx05
17天前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=100010;
int h[N],e[N],w[N],ne[N],idx;
int d[N],n,m;
bool st[N];
queue<int> q;
void add(int x,int y,int z)
{
    e[++idx]=y;
    w[idx]=z;
    ne[idx]=h[x];
    h[x]=idx;
}
int main()
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    memset(d,0x3f,sizeof d);
    d[1]=0;
    q.push(1);
    st[1]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        st[x]=0;
        for(int i=h[x];i;i=ne[i])
        {
            int y=e[i],z=w[i];
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                if(!st[y])
                {
                    q.push(y);
                    st[y]=1;
                }
            }
        }
    }
    if(d[n]==0x3f3f3f3f) printf("impossible");
    else printf("%d",d[n]);
    return 0;
}



lisx05
17天前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=150010;
int h[N],e[N],ne[N],w[N],idx;
int d[N],n,m;
bool v[N];
typedef pair<int,int> PII; 
priority_queue<PII,vector<PII>,greater<PII> >q;
void add(int x,int y,int z)
{
    e[++idx]=y;
    w[idx]=z;
    ne[idx]=h[x];
    h[x]=idx;
}
int main()
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    memset(d,0x7f,sizeof d);
    d[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        if(v[x]) continue;
        v[x]=1;
        for(int i=h[x];i;i=ne[i])
        {
            int y=e[i],z=w[i];
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                q.push(make_pair(d[y],y));
            }
        }
    }
    if(d[n]==0x7f7f7f7f) printf("-1");
    else printf("%d",d[n]);
    return 0;
}