本文主要是介绍ACM-ICPC 2018 南京赛区网络预赛 L Magical Girl Haze(分层图+Dijkstra堆优化)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://nanti.jisuanke.com/t/31001
题目大意：给一张有向图，给把k条边权值变0的机会，问1~n最短路
题目思路：把原先的dist改成二维，第二维表示删几条边， 然后迪杰斯特拉的松弛也分成两部分，一个是本身的松弛，还有一个是送到下一层，由于每一层内，最小的那个松弛以后他松弛的点继续松弛，这样就等效于只删了一条边，如此一直松弛。
以下是代码：
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define MAXN 100005
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
struct Edge{int to,w,next;
}edge[MAXN<<1];
struct node{int v,c,cnt;bool operator <(const node &r)const{return c>r.c;}
}a;
int head[MAXN],tot,k;
void addedge(int u,int v,int w){edge[tot].to=v,edge[tot].w=w,edge[tot].next=head[u],head[u]=tot++;
}
bool vis[MAXN][15];
ll dist[MAXN][15];
void dij(int n,int s){memset(vis,false,sizeof(vis));memset(dist,0x3f,sizeof(dist));priority_queue<node>q;while(!q.empty())q.pop();dist[s][0]=0;a.v=s,a.c=a.cnt=0;q.push(a);while(!q.empty()){node temp=q.top();q.pop();int u=temp.v,cnt=temp.cnt;if(vis[u][cnt])continue;vis[u][cnt]=1;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to,w=edge[i].w;if(!vis[v][cnt]&&dist[v][cnt]>dist[u][cnt]+w){dist[v][cnt]=dist[u][cnt]+w;a.v=v,a.c=dist[v][cnt],a.cnt=cnt;q.push(a);}if(cnt<k&&dist[v][cnt+1]>dist[u][cnt]){dist[v][cnt+1]=dist[u][cnt];a.v=v,a.c=dist[u][cnt],a.cnt=cnt+1;q.push(a);}}}
}
int main()
{int t,n,m,u,v,w;scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&k);tot=0;memset(head,-1,sizeof(head));while(m--){scanf("%d%d%d",&u,&v,&w);addedge(u,v,w);}dij(n,1);printf("%lld\n",dist[n][k]);}return 0;
}
这篇关于ACM-ICPC 2018 南京赛区网络预赛 L Magical Girl Haze(分层图+Dijkstra堆优化)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
