最短距离， dijkstra算法
本题要点：
1、图的建立： 假想有一个原点 0， MaxN = 110， 用邻接矩阵来存图。
扫描输入的数据，记录第i点的level 和 val（需要的金币）。假设当前点是i，i点的替换点是 j，
存在一条边，由 j点指向 i点， 边的权值是这个代替点额外需要的金币。当然，原点 0 指向每一点i， 权值为第i点需要的金币。
2、 然后，通过 vis 数组，来限定点的等级。以第i个点的等级为基础， 分别求 0 点到 1 点的最短距离。
以第i点的level 为最小值，等级的取值范围 [level[i], level + m]。
扫描所有的点，level 不在这个范围内的 点j， vis[j] = true;
然后求出第i点为基础等级时候，原点0 到 1 点的距离 （ 也就是d[1]的大小 ）
3、 取出d[1] 的最小值，就是答案。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 110;
int n, m;
int cost[MaxN][MaxN];
int level[MaxN], val[MaxN], d[MaxN]; // val[i]表示第i点的需要的金币
bool vis[MaxN];void dijkstra() //这里假想出来一个原点0， 计算0点到 1 ~ n 这n个点的最短路径
{
memset(d, 0x3f, sizeof(d));d[0] = 0;for(int i = 1; i <= n; ++i) //重复 n 次{
int x = -1;for(int j = 0; j <= n; ++j){
if(!vis[j] && (-1 == x || d[j] < d[x])){
x = j;}}if(-1 == x){
return;}vis[x] = true;for(int y = 0; y <= n; ++y){
if(!vis[y]){
d[y] = min(d[y], d[x] + cost[x][y]);}}}
// printf("ii = %d, d[1] = %d\n", ii, d[1]);
}int main()
{
while(scanf("%d%d", &m, &n) != EOF){
memset(cost, 0x3f, sizeof(cost));for(int i = 1; i <= n; ++i){
cost[i][i] = 0;}for(int i = 1; i <= n; ++i){
int k, j, w;scanf("%d%d%d", &val[i], &level[i], &k);cost[0][i] = val[i]; //原点到i点的费用for(int t = 0; t < k; ++t){
scanf("%d%d", &j, &w);cost[j][i] = min(cost[j][i], w);}}int ans = 0x3f3f3f3f;for(int i = 1; i <= n; ++i) //以第i个点的等级为基础， 分别求 0 点到 1 点的最短距离{
memset(vis, false, sizeof(vis)); int min_level = level[i];for(int j = 1; j <= n; ++j){
if(level[j] < min_level || level[j] > min_level + m){
vis[j] = true;}}dijkstra();ans = min(ans, d[1]);}printf("%d\n", ans);}return 0;
}/* 1 4 10000 3 2 2 8000 3 5000 1000 2 1 4 200 3000 2 1 4 200 50 2 0 *//* 5250 */