ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze(dijkstra+分层最短路)
思路来源
https://blog.csdn.net/zhangche0526/article/details/62881066
题意
给你n个城市,m条边,
共有k次免费机会,可以将其中k条边的权值变为0,
求点1到点n的最短路。
题解
(百度 分层图最短路问题 发现是原题 QAQ)
首先,感谢思路来源的答主,
画了个图,让我懂了这题的原理,
本来看了好几篇都不懂的 QAQ
建(k+1)层图,依次对应第0层,第1层,…,第k层,
每层内部,对应原来的图;层与层之间,建权值为0的边,
即我们在建图的时候,
层内,仍然是u->v的关系,权值为w,
层间,也是u->v的关系,但权值是0,
这代表,可以用一次机会,实现i层向(i+1)层的跨层。
至于这一次用在哪里,无需深究。
第i层,代表已用了i次免费机会,
显然,免费机会,不用白不用,
所以第k层的终点,就是最优解,
第0层的源点,到第k层的终点,就是最短路
心得
我们共新建了k层图,包括初始图共(k+1)层图,
每层的点是N个,共N*(k+1)个点,
故,点开110W即可。
(k+1)层图,共(k+1)*m条边,
每两层之间,有下层u依照原图连向上层v的全0边共m条,共k*m条边,
总计(2*k+1)*m条边。
故,边开420W即可。
偶槽 这竟然是原题是原题是原题啊 BZOJtql
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
const int INF=0x3f3f3f3f;
const int maxn=1e5+10;
const int mod=1e9+7;
const int MOD=998244353;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int>
#define si set<int>
#define pii pair<ll,int>
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,m,k,head[2000005],cnt;
ll dis[2000005],ans;
bool vis[2000005];
struct edge{int to,nex;ll w;}e[8000005];
priority_queue<pii,vector<pii>,greater<pii> >q;
void init()
{
for(int i=0;i<2000003;++i)
dis[i]=8e18;
ans=8e18;
cnt=0;
mem(head,-1);
mem(vis,0);
}
void add(int u,int v,ll w)
{
e[cnt].to=v;
e[cnt].w=w;
e[cnt].nex=head[u];
head[u]=cnt++;
}
void dijkstra(int u)
{
while(!q.empty())q.pop();
for(int j=head[u];~j;j=e[j].nex)
{
int v=e[j].to;
ll w=e[j].w;
dis[v]=w;
q.push(pii(dis[v],v));
//printf("v:%d %lf\n",v,dis[v]);
}
dis[u]=0;vis[u]=1;
while(!q.empty())
{
pii tmp=q.top();
q.pop();
int pos=tmp.second;
ll d=tmp.first;
//printf("pos:%d\n",pos);
if(vis[pos])continue;
vis[pos]=1;
for(int i=head[pos];~i;i=e[i].nex)
{
int v=e[i].to;
ll w=e[i].w;
if(dis[v]>dis[pos]+w)
{
dis[v]=dis[pos]+w;
q.push(pii(dis[v],v));
}
}
}
}
int main()
{
int t;
sci(t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
init();
int u,v;
ll w;
for(int j=1;j<=m;++j)
{
scanf("%d%d%lld",&u,&v,&w);
u--;v--;
for(int i=0;i<=k;++i)
{
add(u+i*n,v+i*n,w);
if(i-k)//这一层还有上层
{
add(u+i*n,v+(i+1)*n,0);
}
}
}
dijkstra(0);
for(int i=0;i<=k;i++)
ans=min(ans,dis[n-1+i*n]);
printf("%lld\n",ans);
}
return 0;
}