题意：略
解析：枚举等级，Dijkstra
#include#include #include using namespace std;const int maxn = 1005;#define INF 0xfffffffint mapp[ maxn ][ maxn ], num[ maxn ][ maxn ], vis[ maxn ], dis[ maxn ], leaval[ maxn ];int m, n, a, b, c, k1, ans;struct node{ int p, l, x;}edge[ maxn ];void Dijkstra(){ ans = edge[ 1 ].p; for( int x = 1; x <= k1; ++x ){ int Min = leaval[ x ] - m; int Max = leaval[ x ]; if( edge[ 1 ].l < Min || edge[ 1 ].l > Max ) continue; memset( vis, 0, sizeof( vis ) ); for( int i = 0; i <= n; ++i ){ dis[ i ] = INF; } // vis[ 1 ] = 1; dis[ 1 ] = 0; for( int i = 1; i <= n; ++i ){ int temp = INF, k; for( int j = 1; j <= n; ++j ){ if( !vis[ j ] &&( temp > dis[ j ] ) && edge[ j ].l >= Min && edge[ j ].l <= Max ){ temp = dis[ k = j ]; } } if( temp == INF ) break; vis[ k ] = 1; for( int j = 1; j <= n; ++j ){ if( !vis[ j ] && dis[ j ] > dis[ k ] + num[ k ][ j ] && edge[ j ].l >= Min && edge[ j ].l <= Max ){ dis[ j ] = dis[ k ] + num[ k ][ j ]; } } } for( int i = 1; i <= n; ++i ){ dis[ i ] += edge[ i ].p; } for( int i = 1; i <= n; ++i ){ if( dis[ i ] < ans ){ ans = dis[ i ]; } } } printf( "%d\n", ans );}int main(){ while( scanf( "%d%d", &m, &n ) != EOF ){ for( int i = 0; i <= n; ++i ){ for( int j = 0; j <= n; ++j ){ num[ i ][ j ] = INF; } } k1 = 1; for( int i = 1; i <= n; ++i ){ scanf( "%d%d%d", &a, &b, &c ); edge[ i ].p = a; edge[ i ].l = b; edge[ i ].x = c; leaval[ k1++ ] = b; for( int j = 1; j <= c; ++j ){ scanf( "%d%d", &a, &b ); num[ i ][ a ] = b; } } Dijkstra(); } return 0;}