[USACO08JAN]电话线Telephone Lines(分层图)/洛谷P1948

这道题其实是分层图，但和裸的分层图不太一样。因为它只要求路径总权值为路径上最大一条路径的权值，但仔细考虑，这同时也满足一个贪心的性质，那就是当你每次用路径总权值小的方案来更新，那么可以保证新的路径权值尽量小。

所以这道题在不删边的情况下可以使用Dij来跑，而删边权的情况就是分层图。

所以就拿分层图来搞好了^_^。

由于这个数据p和k都比较大，所以直接建k+1层图是要爆的，而k+1层图边都一样，我们就用dis[层数（0-k）]来表示。

具体的就是每次Dij转移是要分两种情况：

1.在原层跑，也就是说，在这层中用Dij
2.若下一层边的另一端不够优秀，就用这一层来直接更新，当然就是把这一端的点的解直接复制

大概就是这样了

 #include<queue>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 struct tmp{

 　　int no;

 　　int ler;

 　　int dis;

 　　bool friend operator < (tmp x,tmp y)

 　　{

 　　　　return x.dis>y.dis;

 　　}

 };

 struct pnt{

 　　int no;

 　　int hd;

 　　int dis[];

 　　bool vis[];

 }p[];

 struct ent{

 　　int twd;

 　　int lst;

 　　int vls;

 }e[];

 int n,m,d;

 int cnt;

 priority_queue<tmp>Q;

 void ade(int f,int t,int v)

 {

 　　cnt++;

 　　e[cnt].twd=t;

 　　e[cnt].lst=p[f].hd;

     p[f].hd=cnt;

     e[cnt].vls=v;

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&d);

     for(int i=;i<=n;i++)

     {

         p[i].no=i;

         for(int j=;j<=d;j++)

         {

             p[i].dis[j]=0x3f3f3f3f;

         }

     }

     p[].dis[]=;

     for(int i=;i<=m;i++)

     {

         int a,b,c;

         scanf("%d%d%d",&a,&b,&c);

         ade(a,b,c);

         ade(b,a,c);

     }

     tmp x;

     x.no=;

     x.ler=;

     x.dis=;

     Q.push(x);

     while(!Q.empty())

     {

         x=Q.top();

         Q.pop();

         int nw=x.no;

         int t=x.ler;

         if(x.no==n&&x.ler==d)

         {

             printf("%d\n",x.dis);

             return ;

         }

         if(p[nw].vis[t])continue;

         p[nw].vis[t]=true;

         for(int i=p[nw].hd;i;i=e[i].lst)

         {

             int to=e[i].twd;

             if(p[to].dis[t]>max(p[nw].dis[t],e[i].vls))

             {

                 p[to].dis[t]=max(p[nw].dis[t],e[i].vls);

                 x=(tmp){to,t,p[to].dis[t]};

                 Q.push(x);

             }

             if(p[to].dis[t+]>p[nw].dis[t]&&t<d)

             {

                 p[to].dis[t+]=p[nw].dis[t];

                 x=(tmp){to,t+,p[to].dis[t+]};

                 Q.push(x);

             }

         }

     }

     printf("-1\n");

     return ;

 }

 telephone line

其实，这道题还可以二分来搞，我就不赘述了主要是我太懒了

巴特西

[USACO08JAN]电话线Telephone Lines(分层图)/洛谷P1948

最新文章

热门文章