自动搬运

查看原文

来自洛谷，原作者为

	中国飞鱼 **

搬运于2025-08-24 21:42:03，当前版本为作者最后更新于2017-11-09 16:16:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先对起点和终点分别跑一边SPFA,那么次短路一定是:

某一条边的w + 起点到该边一端点的最短路 + 终点到该边另一端点的最短路

(注意到反复经过的边必然只有一条并且反复过不超过3次,否则绝不是次短路,那么我们假设全图最短路是dist[S][i]+cost[i][j]+dsit[j][T],反复经过边的情况可以处理成:dist[S][j]+cost[i][j]+dist[i][T])

因此再枚举每一条边,计算次短路并把与全图最短路长度相等的筛掉即可

比较坑的一点:题目有重边,不能简单统计节点的出现次数来判断是否合法(>=k),具体见代码:

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=5002,M=100002,INF=1e9+7;
int n,m,k,cnt,u,v,w,mindist,secdist=INF;//mindist最短路,secdist次短路
int last[N],t[N],dist[2][N];//t是每个点的出边数
bool used[N],vis[N];
struct edg{
    int to,next,w;
}edge[2*M];//邻接表
void insert(int u,int v,int w)//连边
{
    edge[++cnt]=(edg){v,last[u],w};last[u]=cnt;
    edge[++cnt]=(edg){u,last[v],w};last[v]=cnt;
}
void SPFA(int S,int op)//op=0是起点的参数,op=1是终点的参数
{
    for(int i=1;i<=n;i++)dist[op][i]=INF,used[i]=0;//初始化
    queue<int> Q;
    Q.push(S);
    used[S]=1;
    dist[op][S]=0;
    while(!Q.empty())
    {
        int now=Q.front();Q.pop();
        used[now]=0;
        for(int i=last[now];i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(dist[op][now]+edge[i].w<dist[op][v]&&t[v]>=k)//筛掉不合法的(即小于k的)
            {
                dist[op][v]=dist[op][now]+edge[i].w;
                if(!used[v]){Q.push(v);used[v]=1;}
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        insert(u,v,w);
    }
    for(int i=2;i<n;i++)//全图扫一遍处理每个点的t值
    {
        memset(vis,0,sizeof(vis));
        for(int j=last[i];j;j=edge[j].next)
        {
            int v=edge[j].to;
            if(!vis[v]){vis[v]=1;t[i]++;}
        }
    }
    t[1]=INF;t[n]=INF;
    SPFA(1,0);
    SPFA(n,1);
    mindist=dist[0][n];
    for(int i=1;i<=n;i++)
    {
        if(t[i]<k)continue;
        for(int j=last[i];j;j=edge[j].next)//枚举每条边
        {
            int v=edge[j].to;
            int len=dist[0][i]+edge[j].w+dist[1][v];
            if(len>mindist&&t[v]>=k)secdist=min(secdist,len);
        }
    }
    printf("%d\n",secdist>=INF?-1:secdist);
    return 0;
}