「BJWC2012」冻结题解

"我要成为魔法少女！"

"那么，以灵魂为代价，你希望得到什么？"

"我要将有关魔法和奇迹的一切，封印于卡片之中"

在这个愿望被实现以后的世界里，人们享受着魔法卡片（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最少需要多长时间。

2.1输入格式

第一行包含三个整数：\(N\),\(M\),\(K\)。

接下来\(M\)行，每行包含三个整数：\(Ai\),\(Bi\),\(Timei\)表示存在一条\(Ai\)与$$Bi之间的双向道路，在不使用 SpellCard 之前提下，通过它需要的时间。

2.2输出格式

输出一个整数，表示从1号城市到\(N\)号城市的最小用时。

因为有k次机会对边权进行修改操作，是分层图擅长的操作，所以果断选择分层图

同时，这道题是一道裸的分层图模板，每一层的建图和原图一样，所以建图很简单

层与层之间的连边的权值w根据题意就是/2，变为原来的一半,那么层与层之间的连接也很简单了

4.1物理建图

  #include<bits/stdc++.h>
  using namespace std;
  const int inf=0x3f3f3f3f;//极大值
  int head[55*55];
  int cnt=0;
  struct edge{//链式前向星
    int v;
    int nex;
    int w;
  }e[1010*55*4];
  void add(int u,int v,int w){//加边
    e[cnt].v=v;//<u,v>表示一条边的两个节点
    e[cnt].w=w;//边权
    e[cnt].nex=head[u];
    head[u]=cnt++;
  }
  int n,m,k;
  int dis[55*55];
  bool vis[55*55];//标记数组，标记是否遍历过
  void dij(int s) {
    memset(vis,0,sizeof(vis));
    memset(dis,inf,sizeof(dis));//清空，很重要!!!
    dis[s]=0;
    //小根堆优化
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    q.push(make_pair(0,s)) ;//pair
    while(!q.empty()) {
        int u=q.top().second;//取第二个
        q.pop();
        if(vis[u]){//跳过
            continue;
        }else{
            vis[u]=1;
            for(int i=head[u];~i;i=e[i].nex){//遍历
                int v=e[i].v;
                if(dis[v]>dis[u]+e[i].w) {
                    dis[v]=dis[u]+e[i].w;
                    q.push(make_pair(dis[v],v));
                }
            }
        }
    }
  }
  int main(){
    //初始化
    memset(head,-1,sizeof(head));
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        //第0层
        add(u,v,w);
        add(v,u,w);
        //建立k层
        for(int j=1;j<=k;j++){
        add(u+j*n-n,v+j*n,w/2);
        add(v+j*n-n,u+j*n,w/2);
        add(u+j*n,v+j*n,w);
        add(v+j*n,u+j*n,w);
        }
    }
    dij(1);
    //循环看不同操作次数的min值
    int ans=inf;
    for(int i=0;i<=k;i++){
        ans=min(ans,dis[n+i*n]);
    }
    cout<<ans<<endl;
    return 0;
  }

4.2逻辑建图

  #include<bits/stdc++.h>
  using namespace std;
  const int maxn=55;//定义
  const int maxk=55;
  int n,m,k;
  int ans=0x7f3f3f3f;//极大值
  int a,b,c;
  int dis[maxn][maxk];
  int vis[maxn][maxk];
  int first[maxn];
  int nex[2010],v[2010],w[2010];//存图数组
  struct node{
    int val;
    int u;
    int tot;
  };
  bool operator<(node a,node b){//优先队列
    return a.val>b.val;
  }
  priority_queue<node> q;
  int cnt;
  void add(int U,int V,int val){//存图
    v[++cnt]=V;
    w[cnt]=val;
    nex[cnt]=first[U];
    first[U]=cnt;
  }
  int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){//加边
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    memset(dis,0x3f,sizeof(dis));//初始化
    dis[1][0]=0;
    q.push({0,1,0});
    while(q.size()){
        int u=q.top().u;
        int tot=q.top().tot;
        q.pop();
        if(vis[u][tot]){//跳过
            continue;
        }
        vis[u][tot]=1;
        //核心代码，牢记
        for(int i=first[u];i;i=nex[i]){
            if(dis[v[i]][tot]>dis[u][tot]+w[i]){
                dis[v[i]][tot]=dis[u][tot]+w[i];
                q.push({dis[v[i]][tot],v[i],tot});
            }
            if(tot<k&&dis[v[i]][tot+1]>dis[u][tot]+w[i]/2){
                dis[v[i]][tot+1]=dis[u][tot]+w[i]/2;
                q.push({dis[v[i]][tot+1],v[i],tot+1});
            }
        }
    }
    for(int i=0;i<=k;i++){
        ans=min(ans,dis[n][i]);
    }
    cout<<ans<<endl;
    return 0;
  }

这篇题解到这就结束啦！！！[完结撒花]