「POJ3662」Telephone Lines

两种解法。

解法一：分层图

用 $dis[i][j]$ 代表到达第 $i$ 个基站，已经使 $j$ 条电缆免费时，所经过的路径上最贵的电缆的花费。

设存在一条从 $from$ 到 $i$ 的边，权值为 $num$ ，于是可以很快推出转移方程：

$$dis[i][j]=max(dis[from][j],num)$$

$$dis[i][j+1]=dis[from][j]$$

于是直接借助 $SPFA$ 求解。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
int n,m,k;
int head[20101],cnt;
int vis[1010][1010],dis[1010][1010];
struct node
{
	int next;
	int to;
	int num;
}e[20101];
struct slice
{
	int u;
	int sum;
};
void add(int from,int to,int num)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	e[cnt].num=num;
	head[from]=cnt;
}
void SPFA()
{
	memset(dis,0x3f,sizeof(dis));
	queue<slice> q;
	dis[1][0]=0;
	vis[1][0]=1;
	slice a;
	a.u=1;
	a.sum=0;
	q.push(a);
	while(!q.empty())
	{
		int u=q.front().u;
		int sum=q.front().sum;
		q.pop();
		vis[u][sum]=0;
		for(int i=head[u];i;i=e[i].next)
		{
			int v=e[i].to;
			if(sum<k&&dis[v][sum+1]>dis[u][sum])
			{
				dis[v][sum+1]=dis[u][sum];
				if(!vis[v][sum+1])
				{
					a.u=v;
					a.sum=sum+1;
					q.push(a);
					vis[v][sum+1]=1;
				}
			}
			if(dis[v][sum]>max(dis[u][sum],e[i].num))
			{
				dis[v][sum]=max(dis[u][sum],e[i].num);
				if(!vis[v][sum])
				{
					a.u=v;
					a.sum=sum;
					q.push(a);
					vis[v][sum]=1;
				}
			}
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	SPFA();
	if(dis[n][k]>=1061109567)
	{
		printf("-1");
		return 0;
	}
	else
		printf("%d",dis[n][k]);
	return 0;
}

解法二：双端队列BFS+二分

因为支付的钱越多时，合法的升级方案一定包含了花费更少的升级方案，说明答案具有单调性，我们可以二分答案。

问题转化为：是否存在一种合法方案，使花费不超过 $mid$。

转化后判定问题非常容易，只用把价格大于 $mid$ 的电缆看作长度为 $1$ 的边，小于的看作长度为 $0$ 的边，然后求 $1\sim N$ 的最短路是否不超过 $K$，我们可以用双端队列 $BFS$ 解决这种边权只有 $0$ 和 $1$ 的最短路问题。

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int head[10001],dis[10001],ex[10001],n,p,k,a,b,len,l=0,r=1000000,mid=0,cnt,ans=1000000;
struct node
{
    int to;
    int next;
    int num;
}faq[100001];
int add(int from,int to,int num)
{
    faq[++cnt].to=to;
    faq[cnt].next=head[from];
    faq[cnt].num=num;
    head[from]=cnt;
}
void spfa()
{
    queue<int> q;
    q.push(1);
    dis[1]=0;
    ex[1]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        ex[u]=0;
        for(int i=head[u];i;i=faq[i].next)
        {
            int v=faq[i].to;
            int w=0;
            if(faq[i].num>mid)
                w=1;
            else
                w=0;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!ex[v])
                {
                    ex[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
    int i,j;
    scanf("%d%d%d",&n,&p,&k);
    for(i=1;i<=p;i++)
    {
        scanf("%d%d%d",&a,&b,&len);
        add(a,b,len);
        add(b,a,len);
    }
    while(l<=r)
    {
        memset(dis,0x3f,sizeof(dis));
        memset(ex,0,sizeof(ex));
        mid=(l+r)/2;
        spfa();
        if(dis[n]>k)
            l=mid+1;
        else
        {
            r=mid-1;
            ans=min(ans,mid);
        }
    }
    if(ans>=1000000)
        printf("-1");
    else
        printf("%d",ans);
    return 0;
}