P4822 [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\) 最少需要多长时间。
对于 \(100\%\) 的数据，保证：
- \(1 \leq K \leq N \leq 50\)，\(M \leq 10^3\)。
- \(1 \leq A_i,B_i \leq N\)，\(2 \leq Time_i \leq 2 \times 10^3\)。
- 为保证答案为整数，保证所有的 \(Time_i\) 均为偶数。
- 所有数据中的无向图保证无自环、重边，且是连通的。
好久没有见到这么友善的最短路了，将状态设为到某个点手上还有几张 SpellCard 然后直接 dijkstra 就好了
有趣的是在这题的
四
倍
经
验 中难度最低(主观认为)的评了蓝，难度最高评了绿 ???
Code:
#include<bits/stdc++.h>
const int N=55;
const int inf=1e9;
using namespace std;
struct Node{
int x,k,val;
bool operator < (const Node &e)const{
return e.val<val;
}
};
vector<tuple<int,int> > E[N];
int n,m,K;
priority_queue<Node> Q;
int dis[N][N],vis[N][N];
void init()
{
for(int i=0;i<N;i++)for(int j=0;j<N;j++)dis[i][j]=inf;
}
void dijkstra()
{
init();
for(int k=K;k>=0;k--)Q.push(Node{1,k,dis[1][k]=0});
while(!Q.empty())
{
Node u=Q.top();Q.pop();
int x=u.x,k=u.k;
//cout<<"dis:"<<x<<" "<<k<<"="<<u.val<<"\n";
if(vis[x][k])continue;
vis[x][k]=1;
for(auto [y,w] : E[x])
{
if(dis[y][k]>dis[x][k]+w)
{
dis[y][k]=dis[x][k]+w;
Q.push({y,k,dis[x][k]+w});
}
if(k&&dis[y][k-1]>dis[x][k]+w/2)
{
dis[y][k-1]=dis[x][k]+w/2;
Q.push({y,k-1,dis[x][k]+w/2});
}
}
}
}
void work()
{
cin>>n>>m>>K;
for(int i=1,x,y,w;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&w);
E[x].emplace_back(y,w);
E[y].emplace_back(x,w);
}
dijkstra();
int ans=inf;
for(int k=K;k>=0;k--)ans=min(ans,dis[n][k]);
printf("%d",ans);
}
int main()
{
//freopen("P4822.in","r",stdin);freopen("P4822.out","w",stdout);
work();
return 0;
}