Dijkstra最短路，每次限制一个等级差，再更新答案。
代码语言：javascript复制#include <cstdio>
#define N 105
#define INF 1e9
int m, n;
int p[N], l[N], x, t, v, g[N][N];
int w, minc, d[N], u[N], ans;
void Dijkstra(int q)
{
for(int i = 1; i <= n; i ){
d[i] = g[1][i];
if(!d[i])d[i]=INF;
u[i]=0;
}
u[1] = 1;
for(int i = 2; i <= n; i )
{
minc = 1e9;
w = 0;
for(int j = 2; j <= n; j )
if(!u[j] && minc >= d[j] && l[j] >= q && l[j] <= q m)
{
minc = d[j];
w = j;
}
if(!w) break;
u[w] = 1;
for(int j = 2; j <= n; j )
if(!u[j] && g[w][j] && d[j] > d[w] g[w][j] && l[j] >= q && l[j] <= q m)
d[j] = d[w] g[w][j];
}
for(int i = 2; i <= n; i )
if(d[i] p[i] < ans &&l[i] >= q && l[i] <= q m)ans = d[i] p[i];
}
int main()
{
scanf("%d%d", &m, &n);
for(int i = 1; i <= n; i )
{
scanf("%d%d%d", &p[i], &l[i], &x);
for(int j = 1; j <= x; j )
{
scanf("%d%d", &t, &v);
g[i][t] = v;
}
}
ans = p[1];
for(int i = l[1] - m; i <= l[1] ; i )
Dijkstra(i);
printf("%dn",ans);
return 0;
}
