从题意中我们知道,最后所有的最短路都会汇集在1号点,也就是说1号点是所有最短路都存在的点,这个条件很重要,这样我们就可以依照1号点来给定区间,比如1号点等级为stp,那么也就是说在所有最短路的这些点都必须满足在[lev-i,lev+M-i]这个区间里面。如果在这个区间内出现的两个点的他们之间的等级差不会超过了M值。
//196K
0MS
#include <stdio.h>
#include <string.h>
#define VM 110
#define EM 10005
const int inf = 0x3f3f3f3f;
struct E
{
to,w,nxt;
}orig[EM],edge[EM];
struct point
{
cost,stp;
}node[VM];
//每种物品的花费和等级
int head1[VM],head[VM],e1,e,M,N,ans;
void addedge1 (int cu,int cv,int cw)
{
= cv;
cw;
= head1[cu];
e1 ++;
}
void addedge (int cu,int cv,int cw)
{
cv;
cw;
= head[cu];
++;
}
int min (int a,int b)
{
> b ? b : a;
}
void Build (int a,int b) //重构图 等级在[a,b]内的边
{
u,v;
<= N;u ++)
if (node[u].stp <=
b&&node[u].stp >=
a)
for (int i = head1[u];i != -1;i = orig[i].nxt)
{
v = orig[i].to;
if (node[v].stp <=
b&&node[v].stp >=
a)
addedge(u,v,orig[i].w);
}
}
void Spfa ()
//spfa求最短路
{
dist[VM],vis[VM],que[VM+10];
i,u,v,front = 0,rear = 0;
(dist,0x3f,sizeof(dist));
(vis,0,sizeof(vis));
0,vis[1] = 1;
= 1;
!= rear)
u = que[front ++];
front = front % VM;
vis[u] = 0;
for (i = head[u];i != -1;i = edge[i].nxt)
{
v = edge[i].to;
if (dist[v] > dist[u] + edge[i].w)
{