【BZOJ1579/Usaco2009 Feb】Revamping Trails 道路升级
题目描述
Farmer John dutifully checks on the cows every day. He traverses some of the M (1 <= M <= 50,000) trails conveniently numbered 1..M from pasture 1 all the way out to pasture N (a journey which is always possible for trail maps given in the test data). The N (1 <= N <= 10,000) pastures conveniently numbered 1..N on Farmer John's farm are currently connected by bidirectional dirt trails. Each trail i connects pastures P1_i and P2_i (1 <= P1_i <= N; 1 <= P2_i <= N) and requires T_i (1 <= T_i <= 1,000,000) units of time to traverse.
He wants to revamp some of the trails on his farm to save time on his long journey. Specifically, he will choose K (1 <= K <= 20) trails to turn into highways, which will effectively reduce the trail's traversal time to 0. Help FJ decide which trails to revamp to minimize the resulting time of getting from pasture 1 to N.
TIME LIMIT: 2 seconds
输入输出格式
输入格式：
* Line 1: Three space-separated integers: N, M, and K
* Lines 2..M+1: Line i+1 describes trail i with three space-separated integers: P1_i, P2_i, and T_i
输出格式：
* Line 1: The length of the shortest path after revamping no more than K edges
输入输出样例
输入样例：
4 4 1
1 2 10
2 4 10
1 3 1
3 4 100
输出样例：
1
说明
K is 1; revamp trail 3->4 to take time 0 instead of 100. The new shortest path is 1->3->4, total traversal time now 1.
解析：
有两种方法。
第一种：递推。
令表示到点
升级了
条道路的最短路长度，用最短路可顺带解决。
第二种：分层图。
这类问题是分层图的一个重要应用。有K条免费边，除了原图外再建K层图。然后对于从每个点出的每一条边，连一条从此点到这条边终点所对应的下一层的点，边权为零，从一层到下一层相当于走了一条免费边。然后跑一遍最短路。
引用一位大佬的图：
代码（递推）：
#include <bits/stdc++.h>
using namespace std;
const int Maxn=10005;
const int Maxm=50005;
int n,m,k,size,ans=1e9;
int first[Maxn],dis[Maxn][21],vis[Maxn];
struct shu{int to,next,len;};
shu edge[Maxm<<1];
struct data{int a,b,c;};
bool operator <(const data &a,const data &b) {return a.c > b.c;}
inline int get_int()
{
int x=0,f=1;
char c;
for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
if(c=='-') f=-1,c=getchar();
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
inline void build(int x,int y,int z)
{
edge[++size].next=first[x];
first[x]=size;
edge[size].to=y,edge[size].len=z;
}
inline void dijkstra()
{
memset(dis,0x3f3f3f,sizeof(dis));
data p,x;p.a=1,p.b=0,p.c=0;
priority_queue<data>q;
q.push(p);
dis[1][0]=0;
while(!q.empty())
{
p = q.top();
q.pop();
for(int u=first[p.a];u;u=edge[u].next)
{
int to=edge[u].to;
if(dis[to][p.b] > p.c + edge[u].len)
{
dis[to][p.b] = p.c + edge[u].len;
x.a=to,x.b=p.b,x.c=dis[to][p.b];
q.push(x);
}
for(int i=1;i<=k;i++)
if(dis[to][i] > dis[p.a][i-1])
{
dis[to][i] = dis[p.a][i-1];
x.a=to,x.b=i,x.c=dis[to][i];
q.push(x);
}
}
}
}
int main()
{
n=get_int(),m=get_int(),k=get_int();
for(int i=1;i<=m;i++)
{
int x=get_int(),y=get_int(),z=get_int();
build(x,y,z),build(y,x,z);
}
dijkstra();
for(int i=0;i<=k;i++) ans=min(dis[n][i],ans);
cout<<ans;
return 0;
}代码（分层图）：
#include <bits/stdc++.h>
using namespace std;
const int Maxn=400005;
const int Maxm=10000010;
int n,m,k,size;
int first[Maxn],dis[Maxn];
struct shu{int to,next,len;};
shu edge[Maxm<<1];
inline int get_int()
{
int x=0,f=1;
char c;
for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
if(c=='-') f=-1,c=getchar();
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
inline void build(int x,int y,int z)
{
edge[++size].next=first[x];
first[x]=size;
edge[size].to=y,edge[size].len=z;
}
inline void dijkstra()
{
memset(dis,0x3f3f3f,sizeof(dis));
priority_queue<pair<int,int> >q;
q.push(make_pair(0,1)),dis[1]=0;
while(!q.empty())
{
int point=q.top().second;
q.pop();
for(int u=first[point];u;u=edge[u].next)
{
int to=edge[u].to;
if(dis[to] > dis[point] + edge[u].len)
{
dis[to] = dis[point] + edge[u].len;
q.push(make_pair(-dis[to],to));
}
}
}
}
int main()
{
n=get_int(),m=get_int(),k=get_int();
for(int i=1;i<=m;i++)
{
int x=get_int(),y=get_int(),z=get_int();
build(x,y,z),build(y,x,z);
for(int j=0;j<=k;j++)
{
build(j*n+x,j*n+y,z),build(j*n+y,j*n+x,z);
if(i!=k) build(j*n+x,(j+1)*n+y,0),build(j*n+y,(j+1)*n+x,0);
}
}
dijkstra();
cout<<dis[n*k+n]<<"\n";
return 0;
}代码（Orz hzwer优秀写法）:
#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;
}