题解 P1948 【[USACO08JAN]电话线Telephone Lines】

· · 题解

虽然这题题解已经有不少了，但是蒟蒻还是想来一发题解qwq

看了看各路神仙的题解，发现大部分都是spfa+二分的答案

但是本蒟蒻看完题目的第一反应就是

这不就是个分层图最短路吗

直接建图开冲

测一波样例...... 输出5？？？

原来是没看题的锅，题目给出的计算规则是只花费路线中最长的一条路的价钱，而不是将所有路径长度相加求出k次免费的总的最短路

那只需要把代码改一下就好了

但是蒟蒻本来就不是很会分层图，卡了半天总是出0......

无奈之下只能换dijkstra+dp切了这题

当然还用了堆优化，总的来说这题还是很水的，就是代码比较难以实现（个人观点）

代码还是最直观的，各位神仙可以结合代码进行理解

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;

const int N=100050,M=10005,inf=(1<<30);
int cnt,to[N],nxt[N],w[N],n,T,head[N],m,flag[M][21],d[M][21];
int read()
{
    int res=0,kkk=1;char ch=' ';
    while(ch<'0'||ch>'9'){
        ch=getchar();
        if(ch=='-')kkk=-1;
    }
    while(ch>='0'&&ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    return res*kkk;
}
struct node{
    int x,d,num;
    friend bool operator < (node p, node q){
        return p.d > q.d;
    }
};
void addedge(int x,int y,int dis)
{
    to[++cnt]=y;
    w[cnt]=dis;
    nxt[cnt]=head[x];
    head[x]=cnt;
}
void add(int x,int y,int z)
{
    addedge(x,y,z);
    addedge(y,x,z);
}
priority_queue <node> q;
void dijkstra()
{
    for(int i=1;i<=n;i++){
        for(int j=0;j<=T;j++)
            d[i][j]=inf;
    }
    d[1][0]=0;
    q.push(node{1,0,0});
    while(!q.empty()){
        node k=q.top();
        q.pop();
        int x=k.x,num=k.num;
        if(flag[x][num])continue;
        flag[x][num]=1;
        for(register int i=head[x];i;i=nxt[i])
        {
            int kk=to[i];
            if(d[kk][num]>max(d[x][num],w[i])){
                d[kk][num]=max(d[x][num],w[i]);
                if(!flag[kk][num])q.push(node{kk,d[kk][num],num});
                }
                if(num<T&&d[kk][num+1]>d[x][num]){
                    d[kk][num+1]=d[x][num];
                    if(!flag[kk][num+1])q.push(node{kk,d[kk][num+1],num+1});
                }
        }
    }
}
int main()
{
    n=read(),m=read(),T=read();
    for(register int i=1;i<=m;i++){
        int l,r,dis;
        l=read(),r=read(),dis=read();
        add(l,r,dis);
    }
    dijkstra();
    if(d[n][T]!=inf)
        printf("%d\n",d[n][T]);
    else printf("-1\n");
    return 0;
}

下面再提供一份分层图最短路的代码

#include <bits/stdc++.h>

using namespace std;

const int N=100050;
int to[N],w[N],n,K,m,cnt,nxt[N],head[N],d[N],vis[N],s,t;
int read(){
    int res=0,kkk=1;char ch=' ';
    while(!isdigit(ch)){ch=getchar();if(ch=='-')kkk=-1;}
    while(isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
    return res*kkk;
}
void qxx(int x,int y,int dis){
    to[++cnt]=y;
    w[cnt]=dis;
    nxt[cnt]=head[x];
    head[x]=cnt;
}
void add(int x,int y,int z){
    qxx(x,y,z),qxx(y,x,z);
}
struct node{
    int x,d;
    friend bool operator<(node x,node y){
        return x.d>y.d;
    }
};
priority_queue<node>q;
void dijkstra(){
    memset(d,63,sizeof(d));
    q.push(node{s,0});
    d[s]=0;
    while(!q.empty()){
        int k=q.top().x;
        q.pop();
        if(vis[k])continue;
        vis[k]=1;
        for(register int i=head[k];i;i=nxt[i]){
            int kk=to[i];
            if(d[kk]>max(d[k],w[i]))
            {
                d[kk]=max(d[k],w[i]);
                if(!vis[kk]){
                    q.push(node{kk,d[kk]});
                }
            }
        }
    }
}
int main()
{
    n=read(),m=read(),K=read();
    s=1,t=n;
    for(register int i=1;i<=m;i++){
        int l=read(),r=read(),q=read();
        add(l,r,q);
        for(register int j=1;j<=K;j++){
            add(j*n+l,j*n+r,q);
            qxx((j-1)*n+l,j*n+r,0);
            qxx((j-1)*n+r,j*n+l,0);
        }
    }
    dijkstra();
    if(d[K*n+t]!=1061109567)//初始化的值若没有改变就说明无解
        printf("%d\n",d[K*n+t]);
    else printf("-1\n");
    return 0;
}

如果有需要的话，可以看看这里，讲解的还是很赞的ovo

虽然最后有神仙告诉蒟蒻二分+spfa就是分层图，但是我还是要发题解qaq