「BJOI2012」 冻结 - 分层图+最短路
题目描述
“我要成为魔法少女!”
“那么,以灵魂为代价,你希望得到什么?”
“我要将有关魔法和奇迹的一切,封印于卡片之中...”
在这个愿望被实现以后的世界里,人们享受着魔法卡片(SpellCard,又名符卡)带来的便捷。
现在,不需要立下契约也可以使用魔法了!你还不来试一试?
比如,我们在魔法百科全书(Encyclopedia of Spells)里用“freeze”作为关键字来查询,会有很多有趣的结果。
例如,我们熟知的Cirno,她的冰冻魔法当然会有对应的 SpellCard 了。 当然,更加令人惊讶的是,居然有冻结时间的魔法,Cirno 的冻青蛙比起这些来真是小巫见大巫了。
这说明之前的世界中有很多魔法少女曾许下控制时间的愿望,比如 Akemi Homura、Sakuya Izayoi、...
当然,在本题中我们并不是要来研究历史的,而是研究魔法的应用。
我们考虑最简单的旅行问题吧: 现在这个大陆上有 N 个城市,M 条双向的道路。城市编号为 1~N,我们在 1 号城市,需要到 N 号城市,怎样才能最快地到达呢?
这不就是最短路问题吗?我们都知道可以用 Dijkstra、Bellman-Ford、Floyd-Warshall等算法来解决。
现在,我们一共有 K 张可以使时间变慢 50%的 SpellCard,也就是说,在通过某条路径时,我们可以选择使用一张卡片,这样,我们通过这一条道路的时间就可以减少到原先的一半。需要注意的是:
- 在一条道路上最多只能使用一张 SpellCard。
- 使用一张SpellCard 只在一条道路上起作用。
- 你不必使用完所有的 SpellCard。
给定以上的信息,你的任务是:求出在可以使用这不超过 K 张时间减速的SpellCard 之情形下,从城市1 到城市N最少需要多长时间。
分析
分层图经典模型,将图重建k层,每层之间的连边为权值减半,跑最短路即可。
如图,1、2、3为原图的节点,4、5、6为第一层的节点,分别与原图对应,每层之间建的边,为原边权的一半,说明走这条路用了卡片。最后统计答案时不能只统计第k层的节点,应该统计每一层与n对应的节点,因为可能用不到k张卡片。
代码
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std;
int h[5500],cnt;
int dis[5500];
int vis[5500];
int n,m,k,s,t,ans;
struct node {
int to,next,weight;
}e[1000000<<1];
struct node1 {
int d,x;
friend bool operator<(node1 a,node1 b) {
return a.d>b.d;
}
};
void add(int x,int y,int z) {
e[++cnt]=(node){y,h[x],z};
h[x]=cnt;
}
void dijkstra() {
memset(dis,127/2,sizeof(dis));
priority_queue<node1> q;
dis[1]=0;
q.push((node1){0,1});
while (!q.empty()) {
int x=q.top().x;
q.pop();
if (vis[x]) continue;
vis[x]=1;
for (int i=h[x];i;i=e[i].next) {
int y=e[i].to;
if (dis[y]>dis[x]+e[i].weight) {
dis[y]=dis[x]+e[i].weight;
q.push((node1){dis[y],y});
}
}
}
}
int main() {
scanf("%d%d%d",&n,&m,&k);
for (int i=1,a,b,c;i<=m;i++) {
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
for (int j=1;j<=k;j++) {
add(a+n*(j-1),b+n*j,c/2);//上一层(j-1)到这一层(j)建边
add(b+n*(j-1),a+n*j,c/2);
add(a+n*j,b+n*j,c);//本层之间建边
add(b+n*j,a+n*j,c);
}
}
dijsktra();
ans=0x3f3f3f3f;
for (int i=1;i<=k+1;i++)
ans=min(ans,dis[n*i]);
printf("%d",ans);
return 0;
}
上一篇: MySQL 8.0.19安装教程(windows 64位)
下一篇: 最短路——玛丽卡