【BZOJ 1579】 1579: [Usaco2009 Feb]Revamping Trails 道路升级 （最短路）

时间：2021-03-18 18:08:39

1579: [Usaco2009 Feb]Revamping Trails 道路升级

Description

每天,农夫John需要经过一些道路去检查牛棚N里面的牛. 农场上有M(1<=M<=50,000)条双向泥土道路,编号为1..M. 道路i连接牛棚P1_i和P2_i (1 <= P1_i <= N; 1 <= P2_i<= N). John需要T_i (1 <= T_i <= 1,000,000)时间单位用道路i从P1_i走到P2_i或者从P2_i 走到P１_i 他想更新一些路经来减少每天花在路上的时间.具体地说,他想更新K (1 <= K <= 20)条路经，将它们所须时间减为０．帮助FJ选择哪些路经需要更新使得从１到N的时间尽量少.

Input

* 第一行: 三个空格分开的数: N, M, 和 K * 第2..M+1行: 第i+1行有三个空格分开的数：P1_i, P2_i, 和 T_i

Output

* 第一行: 更新最多Ｋ条路经后的最短路经长度．

Sample Input

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

Sample Output

1

HINT

K是1; 更新道路3->4使得从３到４的时间由１００减少到０. 最新最短路经是1->3->4,总用时为１单位. N<=10000

Source

【分析】

　　就是一个分层图最短路，spfa过不了。。所以这是我第一次打迪杰斯特拉？？？

　　dij：分st，ed，两个联盟，每次找dis最小的x加入st联盟，根据他连出去的边更新dis，然后继续做。。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 using namespace std;

 #define Maxn 10010

 #define Maxm 50010

 #define Maxk 25

 #define INF 0xfffffff

 struct node

 {

     int x,y,c,next;

 }t[*Maxm];int len=;

 int first[Maxn];

 int n,m,k;

 void ins(int x,int y,int c)

 {

     t[++len].x=x;t[len].y=y;t[len].c=c;

     t[len].next=first[x];first[x]=len;

 }

 int mymin(int x,int y) {return x<y?x:y;}

 int id[Maxn][Maxk],wh[Maxn*Maxk][];

 int cnt=;

 struct hp

 {

     int d,x;

     friend bool operator < (hp x,hp y)

     {

         return x.d>y.d;

     }

 };

 bool mark[Maxn*Maxk];

 int dis[Maxn*Maxk];

 priority_queue<hp > q;

 void dij(int st)

 {

     while(!q.empty()) q.pop();

     memset(mark,,sizeof(mark));

     memset(dis,,sizeof(dis));

     q.push((hp){,st});dis[st]=;

     while(!q.empty())

     {

         while(!q.empty()&&mark[q.top().x]) q.pop();

         if(q.empty()) break;

         hp x=q.top();q.pop();

         int xx=wh[x.x][],kk=wh[x.x][];

         mark[x.x]=;

         for(int i=first[xx];i;i=t[i].next)

         {

             int y=t[i].y;

             if(mark[id[y][kk]]) continue;

             if(dis[id[y][kk]]>dis[x.x]+t[i].c)

             {

                 dis[id[y][kk]]=dis[x.x]+t[i].c;

                 q.push((hp){dis[id[y][kk]],id[y][kk]});

             }

             if(kk<k)

             {

                 if(dis[id[y][kk+]]>dis[x.x])

                 {

                     dis[id[y][kk+]]=dis[x.x];

                     q.push((hp){dis[id[y][kk+]],id[y][kk+]});

                 }

             }

         }

     }

 }

 int main()

 {

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

     memset(first,,sizeof(first));

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

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

         id[i][j]=++cnt,wh[cnt][]=i,wh[cnt][]=j;

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

     {

         int x,y,c;

         scanf("%d%d%d",&x,&y,&c);

         ins(x,y,c);ins(y,x,c);

     }

     dij(id[][]);

     int ans=INF;

     for(int i=;i<=k;i++) ans=mymin(ans,dis[id[n][i]]);

     printf("%d\n",ans);

     return ;

 }

2017-01-15 10:48:33

相关文章