首页 > 代码库 > bzoj 1579: [Usaco2009 Feb]Revamping Trails 道路升级 优先队列+dij
bzoj 1579: [Usaco2009 Feb]Revamping Trails 道路升级 优先队列+dij
1579: [Usaco2009 Feb]Revamping Trails 道路升级
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 1768 Solved: 481
[Submit][Status][Discuss]
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
思路：dp；
dp[i][j]表示从1-i使用了更新j次的最少距离；
dp[v][j]=min(dp[i][j]+w,dp[i][j-1]);
加一维求最短路，优先队列优化；
#include<bits/stdc++.h>using namespace std;#define ll long long#define mod 1000000007#define pi (4*atan(1.0))const int N=1e5+10,M=4e6+10,inf=1e9+10;const ll INF=1e18+10;struct is{ int v,w; int next;}edge[N*4];int head[N*4],si;int flag[N][23];int d[N][23];struct point{ int pos,dis; point(int a,int b){pos=b;dis=a;} friend bool operator <(point x,point y) { return x.dis>y.dis; }};void add(int u,int v,int w){ si++; edge[si].v=v; edge[si].w=w; edge[si].next=head[u]; head[u]=si;}void dij(int n,int k){ priority_queue<point>q; point a(0,1); q.push(a); while(!q.empty()) { point v=q.top(); q.pop(); int x=(v.pos)%(n+1); int y=(v.pos)/(n+1); if(flag[x][y])continue; flag[x][y]=1; for(int i=head[x];i;i=edge[i].next) { int vv=edge[i].v; if(d[vv][y]>d[x][y]+edge[i].w) { d[vv][y]=d[x][y]+edge[i].w; q.push(point(d[vv][y],y*(n+1)+vv)); } if(y==k)continue; if(d[vv][y+1]>d[x][y]) { d[vv][y+1]=d[x][y]; q.push(point(d[vv][y+1],(y+1)*(n+1)+vv)); } } } printf("%d\n",d[n][k]);}void init(){ si=0; memset(head,0,sizeof(head)); memset(flag,0,sizeof(flag)); for(int i=1;i<N;i++) for(int t=0;t<21;t++) d[i][t]=inf; d[1][0]=0;}int main(){ int x,y,z,i,t; while(~scanf("%d%d%d",&x,&y,&z)) { init(); for(i=0;i<y;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } dij(x,z); } return 0;}
bzoj 1579: [Usaco2009 Feb]Revamping Trails 道路升级 优先队列+dij
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。