本文主要是介绍ACM-ICPC 2018 南京赛区网络预赛__L. Magical Girl Haze 【Dijkstra算法+分层图思想】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
- 1000ms
- 262144K
There are N cities in the country, and M directional roads from u to v(1≤u,v≤n). Every road has a distance ci. Haze is a Magical Girl that lives in City 1, she can choose no more than K roads and make their distances become 0. Now she wants to go to City N, please help her calculate the minimum distance.
Input
The first line has one integer T(1≤T≤5), then following T cases.
For each test case, the first line has three integers N,M and K.
Then the following M lines each line has three integers, describe a road, Ui,Vi,Ci. There might be multiple edges between u and v.
It is guaranteed that N≤100000,M≤200000,K≤10,
0 ≤Ci≤1e9. There is at least one path between City 1 and City N.
Output
For each test case, print the minimum distance.
样例输入
1
5 6 1
1 2 2
1 3 4
2 4 3
3 4 1
3 5 6
4 5 2样例输出
3题目来源
ACM-ICPC 2018 南京赛区网络预赛
题目大意：有N个城市，M条有向边，城市之间可能有多条边，你可以选择让至多K条边的长度变为0，问最好的情况下，城市1到城市N的最短路径为多少
题解：Dijkstra算法+分层图思想，具体看代码来理解分层图思想
AC的C++代码：
#include<iostream>
#include<vector>
#include<queue>
#include<cstring> using namespace std;typedef long long ll;const int INF=0x3f3f3f3f;
const int N=100003;struct Edge{//边 int v,w;//起点到终点v的花费为w Edge(int v,int w):v(v),w(w){}
};struct Node{int u;int w;Node(){}Node(int u,int w):u(u),w(w){}bool operator<(const Node &a)const//使用优先队列，故将<重载为大于含义 {return w>a.w;}
};vector<Edge>g[N];
ll dist[N][11];//dist[i][j]表示在使得j条边为0的情况下源点到结点i的最短路
bool vis[N][11];void dijkstra(int s,int n,int k)//源点为s，共有n个结点 可以选择k条边为0
{priority_queue<Node>q;memset(vis,false,sizeof(vis));memset(dist,INF,sizeof(dist));dist[s][0]=0;q.push(Node(s,0));while(!q.empty()){Node e=q.top();q.pop();int z=e.u/(n+1);//z表示使z条边的长度为0 int u=e.u%(n+1);//u表示当前结点编号 if(!vis[u][z]){//如果还未用dist[u][z]更新其他状态就进行更新 vis[u][z]=true;int num=g[u].size();//与u相连的点有num个 for(int i=0;i<num;i++){int v=g[u][i].v;//v为与u相连的点if(vis[v][z])//如果dist[u][z]已经得到了就跳过 continue;int c=g[u][i].w;//c表示结点u到结点v的距离 //选择1：不让这条边为0if(dist[v][z]>dist[u][z]+c){ dist[v][z]=dist[u][z]+c;/*第一个参数 z*(n+1)+v是为了使得z可以通过e.u/(n+1)得到，u可以 通过e.u%(n+1)得到 */ q.push(Node(z*(n+1)+v,dist[v][z]));}if(z==k)//如果已经使k条边为0，就跳过 continue;//选择2：让这条边为0，则dist[v][z]变为dist[v][z+1]因为多让一条边变为0 if(dist[v][z+1]>dist[u][z]){ dist[v][z+1]=dist[u][z];q.push(Node((z+1)*(n+1)+v,dist[v][z+1]));}}}}
}int main()
{int t,n,m,a,b,k,c;scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&k);for(int i=0;i<=n;i++)g[i].clear();while(m--){scanf("%d%d%d",&a,&b,&c);g[a].push_back(Edge(b,c));}dijkstra(1,n,k);printf("%lld\n",dist[n][k]);}return 0;
}
这篇关于ACM-ICPC 2018 南京赛区网络预赛__L. Magical Girl Haze 【Dijkstra算法+分层图思想】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
