原题链接
前置知识
- Dijkstra
- 链式前向星
- 虚拟源点
分析
本题的难点在于如何建图将原问题抽象成一个最短路问题以及如何处理等级限制。
以下为样例建图示意
最后只需要枚举允许的等级区间,在每一个区间以超级源点为起点跑一遍Dijkstra取所有答案的min,便是最终答案。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 105,M = N * N,INF = 0x3f3f3f3f;
int h[N],ne[M],e[M],w[M],idx = 1;
int m,n,level[N],dis[N];
bool st[N];
void add(int a,int b,int c)
{
e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
int djk(int l,int r)
{
memset(dis,0x3f,sizeof dis);
memset(st,0,sizeof st);
priority_queue<PII,vector<PII>,greater<PII>> heap;
dis[0] = 0;
heap.push({0,0});
while(heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second;
if(st[ver]) continue;
st[ver] = true;
for(int i=h[ver];i!=-1;i = ne[i])
{
int num = e[i];
if(dis[num] > dis[ver] + w[i] && level[num] >= l && level[num] <= r)
{
dis[num] = dis[ver] + w[i];
heap.push({dis[num],num});
}
}
}
return dis[1];
}
int main()
{
memset(h,-1,sizeof h);
cin>>m>>n;
for(int i=1;i<=n;i++)
{
int p,l,x;
cin>>p>>l>>x;
level[i] = l;
add(0,i,p); //超级源点
while(x--)
{
int num,cost;
cin>>num>>cost;
add(num,i,cost);
}
}
int res = INF;
for(int i=level[1]-m;i<=level[1];i++) res = min(res,djk(i,i+m));
cout<<res<<endl;
return 0;
}
想想你的文章写的特别好https://www.ea55.com/
叼茂SEO.bfbikes.com
叼茂SEO.bfbikes.com