「BZOJ1579」[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
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
题解
分层图+dj+堆
此题spfa似乎过不了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include<iostream> #include<cstdio> #include<cstring> #define inf 0x7fffffff using namespace std; int n,m,k,cnt,sz; int head[10001]; int pl[10001][21],d[10001][21]; bool mark[10001][21]; struct heap{int x,y,v;}hp[200001]; struct edge{int to,next,v;}e[100001]; void insert(int u,int v,int w) {cnt++;e[cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;} void pushup(int x) { while(x>1&&hp[x].v<hp[x>>1].v) { swap(hp[x],hp[x>>1]); pl[hp[x].x][hp[x].y]=x; x>>=1; } pl[hp[x].x][hp[x].y]=x; } void pushdown(int x) { while((x<<1)<=sz) { int next=(x<<1); if(hp[next].v<hp[x].v||(next<sz&&hp[next|1].v<hp[x].v)) { if(next<sz&&hp[next].v>hp[next|1].v) next|=1; swap(hp[x],hp[next]); pl[hp[x].x][hp[x].y]=x; x=next; } else break; } pl[hp[x].x][hp[x].y]=x; if(hp[sz].v==inf)sz--; } void push(int x,int y,int v) { sz++;hp[sz].x=x;hp[sz].y=y;hp[sz].v=v; pushup(sz); } void dj() { n*=(k+1); memset(d,127,sizeof(d)); d[1][0]=0; push(1,0,0);mark[1][0]=1; for(int i=1;i<n;i++) { int x=hp[1].x,y=hp[1].y; mark[x][y]=1; hp[1].v=inf;pushdown(1); for(int j=head[x];j;j=e[j].next) { if(!mark[e[j].to][y]&&d[e[j].to][y]>d[x][y]+e[j].v) { d[e[j].to][y]=d[x][y]+e[j].v; if(!pl[e[j].to][y])push(e[j].to,y,d[e[j].to][y]); else { int t=pl[e[j].to][y];hp[t].v=d[e[j].to][y]; pushup(t); } } if(y<k&&!mark[e[j].to][y+1]&&d[e[j].to][y+1]>d[x][y]) { d[e[j].to][y+1]=d[x][y]; if(!pl[e[j].to][y+1])push(e[j].to,y+1,d[e[j].to][y+1]); else { int t=pl[e[j].to][y+1];hp[t].v=d[e[j].to][y+1]; pushup(t); } } } } n/=(k+1); } int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); insert(u,v,w);insert(v,u,w); } dj(); int ans=inf; for(int i=0;i<=k;i++)ans=min(ans,d[n][i]); printf("%d",ans); return 0; } |
Subscribe
计数器 9854487
OI 课件=>
OI 课件=>