头像

itdef


访客:71027

离线:3小时前



itdef
12小时前

题目描述

德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪!!!

他们的德克萨斯长角牛吃起来不错,可是它们并不是很擅长生产富含奶油的乳制品。

农夫John此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任,以减轻德克萨斯人忍受酷暑的痛苦。

John已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。

这些路线包括起始点和终点一共有 T 个城镇,为了方便标号为 1 到 T。

除了起点和终点外的每个城镇都由 双向道路 连向至少两个其它的城镇。

每条道路有一个通过费用(包括油费,过路费等等)。

给定一个地图,包含 C 条直接连接 2 个城镇的道路。

每条道路由道路的起点 Rs,终点 Re 和花费 Ci 组成。

求从起始的城镇 Ts 到终点的城镇 Te 最小的总费用。

输入格式
第一行: 4 个由空格隔开的整数: T,C,Ts,Te;

第 2 到第 C+1 行: 第 i+1 行描述第 i 条道路,包含 3 个由空格隔开的整数: Rs,Re,Ci。

输出格式
一个单独的整数表示从 Ts 到 Te 的最小总费用。

数据保证至少存在一条道路。

数据范围
1≤T≤2500,
1≤C≤6200,
1≤Ts,Te,Rs,Re≤T,
1≤Ci≤1000
输入样例:
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
输出样例:
7


算法1

spfa

C++ 代码

// 123335.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;


const int N = 2510;
const int C = 6500;


int n, m, s, e;

vector<pair<int, int>> g[N];

int dist[N];
bool st[N];

int spfa(int x, int y)
{
    memset(dist, 0x3f, sizeof dist);
    dist[x] = 0;

    queue<int> q;
    q.push(x);
    st[x] = true;

    while (q.size()) {
        int t = q.front(); q.pop();

        st[t] = false;

        for (int i = 0; i < g[t].size(); i++) {
            int b = g[t][i].first;
            int w = g[t][i].second;
            if (dist[b] > dist[t] + w) {
                dist[b] = dist[t] + w;
                if (!st[b]) {
                    q.push(b);
                    st[b] = true;
                }
            }
        }
    }


    return dist[y];
}

int main()
{
    cin >> n >> m >> s >> e;

    for (int i = 0; i < m; i++) {
        int a, c, b;
        cin >> a >> b >> c;
        g[a].push_back({ b,c });
        g[b].push_back({ a,c });
    }

    cout << spfa(s, e);


    return 0;
}





itdef
14小时前

题目描述

农夫John发现了做出全威斯康辛州最甜的黄油的方法:糖。

把糖放在一片牧场上,他知道 N 只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。

当然,他将付出额外的费用在奶牛上。

农夫John很狡猾,就像以前的巴甫洛夫,他知道他可以训练这些奶牛,让它们在听到铃声时去一个特定的牧场。

他打算将糖放在那里然后下午发出铃声,以至他可以在晚上挤奶。

农夫John知道每只奶牛都在各自喜欢的牧场(一个牧场不一定只有一头牛)。

给出各头牛在的牧场和牧场间的路线,找出使所有牛到达的路程和最短的牧场(他将把糖放在那)。

数据保证至少存在一个牧场和所有牛所在的牧场连通。
输入格式

第一行: 三个数:奶牛数 N,牧场数 P,牧场间道路数 C。

第二行到第 N+1 行: 1 到 N 头奶牛所在的牧场号。

第 N+2 行到第 N+C+1 行:每行有三个数:相连的牧场A、B,两牧场间距 D,当然,连接是双向的。
输出格式

共一行,输出奶牛必须行走的最小的距离和。
数据范围

1≤N≤500
,
2≤P≤800,
1≤C≤1450,
1≤D≤255

样例
输入样例:

3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

输出样例:

8


算法1

我们需要
一个比较快的图最短路算法,
尝试以每个农场作为放置糖的位置,牛坐过去的最短路径和
这里使用spfa

C++ 代码

// 112355.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

/*
输入样例:
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
输出样例:
8
*/

int n, p,c;
const int N = 510;
const int P = 810;
const int C = 1510;


int Point[N];

const int INF = 0x3f3f3f3f;

int dist[P];
bool st[P];
vector<pair<int, int>> g[P];


int spfa(int x)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);

    dist[x] = 0;

    queue<int>q;
    q.push(x);
    st[x] = true;

    while (q.size()) {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = 0; i < g[t].size(); i++) {
            int j = g[t][i].first;
            int w = g[t][i].second;

            if (dist[j] > dist[t] + w) {
                dist[j] = dist[t] + w;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    int sum = 0;

    for (int i = 0; i < n; i++) {
        if(dist[Point[i]] == INF) return INF;
        sum += dist[Point[i]];
    }

    return sum;
}



int main()
{
    cin >> n >> p >> c;
    for (int i = 0; i < n; i++) {
        cin >> Point[i];
    }

    for (int i = 0; i < c; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({ b,c });
        g[b].push_back({ a,c });
    }

    int ans = 99999999;
    for (int i = 1; i <= p; i++) {
        ans = min(ans, spfa(i));
    }

    cout << ans << endl;

    return 0;
}




itdef
2天前

题目描述

战争时期,前线有 n 个哨所,每个哨所可能会与其他若干个哨所之间有通信联系。

信使负责在哨所之间传递信息,当然,这是要花费一定时间的(以天为单位)。

指挥部设在第一个哨所。

当指挥部下达一个命令后,指挥部就派出若干个信使向与指挥部相连的哨所送信。

当一个哨所接到信后,这个哨所内的信使们也以同样的方式向其他哨所送信。
信在一个哨所内停留的时间可以忽略不计。

直至所有 n 个哨所全部接到命令后,送信才算成功。

因为准备充足,每个哨所内都安排了足够的信使
(如果一个哨所与其他 k 个哨所有通信联系的话,这个哨所内至少会配备 k 个信使)。

现在总指挥请你编一个程序,计算出完成整个送信过程最短需要多少时间。

输入格式
第 1 行有两个整数 n 和 m,中间用 1 个空格隔开,分别表示有 n 个哨所和 m 条通信线路。

第 2 至 m+1 行:每行三个整数 i、j、k,中间用 1 个空格隔开,
表示第 i 个和第 j 个哨所之间存在 双向 通信线路,且这条线路要花费 k 天。

输出格式
一个整数,表示完成整个送信过程的最短时间。

如果不是所有的哨所都能收到信,就输出-1。

数据范围
1≤n≤100,
1≤m≤200,
1≤k≤1000
输入样例:
4 4
1 2 4
2 3 7
2 4 1
3 4 6
输出样例:
11

算法1

单元最短路模板

C++ 代码

// 11123.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 300;

int g[N][N];
bool st[N];
int dist[N];
int n, m;

void dij()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (t == -1 || dist[t] > dist[j])) {
                t = j;
            }
        }
        st[t] = true;

        for (int j = 1; j <= n; j++) {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }

    return;
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = (c);
        g[b][a] = (c);
    }

    dij();
    int ans = -1;
    for (int i = 1; i <= n; i++) {
        ans = max(dist[i], ans);
    }
    if (ans == 0x3f3f3f3f) ans = -1;
    cout << ans << endl;
    return 0;
}






itdef
2天前

平时习惯使用stl写邻接表,
链式前向星有一定了解。

但是Y总这里的代码
就不太明白为什么used[i]与used[i^1]能表示两条互相反边的边

代码


void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    for (int &i = h[u]; ~i;)
    {
        if (used[i])
        {
            i = ne[i];
            continue;
        }

        used[i] = true;
        if (type == 1) used[i ^ 1] = true;



itdef
2天前

所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。

是不是应该是
所有栅栏都是连通的(也就是你可以从任意一个栅栏到达其连接的所有栅栏)。




itdef
4天前

题目描述

给定一个N行N列的棋盘,已知某些格子禁止放置。

求最多能往棋盘上放多少块的长度为2、宽度为1的骨牌,骨牌的边界与格线重合(骨牌占用两个格子),
并且任意两张骨牌都不重叠。

输入格式
第一行包含两个整数N和t,其中t为禁止放置的格子的数量。

接下来t行每行包含两个整数x和y,表示位于第x行第y列的格子禁止放置,行列数从1开始。

输出格式
输出一个整数,表示结果。

数据范围
1≤N≤100
输出样例:
8 0
输出样例:
32

算法1

棋盘的格子分为黑白两种属性,那么一个骨牌如果能放置在棋盘上,必然覆盖的是一个黑格子一个白格子
将黑白格子看做点,每个骨牌看作为边,那么就是一个二分图最大匹配

C++ 代码

// 1231324.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <cstring>



using namespace std;

int n, m;

const int N = 110;

bool g[N][N];
bool st[N][N];
pair<int, int> match[N][N];

/*
1≤N≤100
输出样例:
8 0
输出样例:
32
*/

int addx[4] = { 1,0,-1,0 };
int addy[4] = { 0,1,0,-1 };

bool find(int x, int y)
{
    for (int i = 0; i < 4; i++) {
        int newx = x + addx[i];
        int newy = y + addy[i];

        if (newx >=1 && newx <= n && newy>=1 && newy <= n && 
            g[newx][newy] == false &&st[newx][newy] == false) 
        {
            st[newx][newy] = true;
            if (match[newx][newy].first == -1 || 
                find(match[newx][newy].first, match[newx][newy].second)) 
            {
                match[newx][newy] = { x,y };
                return true;
            }
        }
    }

    return false;
}



int main()
{
    cin >> n >> m;

    while (m--) {
        int a, b;
        cin >> a >> b;
        g[a][b] = true;
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            match[i][j].first = -1;
            match[i][j].second = -1;
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            //偶点 并且 该点无障碍
            if ((i + j) % 2 == 1 && g[i][j] == false) {
                memset(st, 0, sizeof st);
                if (find(i, j)) res++;
            }
        }
    }

    cout << res << endl;

    return 0;
}





itdef
5天前

题目描述

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。
每一天,我们都会按给出重量的顺序往传送带上装载包裹。
我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

 

示例 1:

输入:weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出:15
解释:
船舶最低载重 15 就能够在 5 天内送达所有包裹,如下所示:
第 1 天:1, 2, 3, 4, 5
第 2 天:6, 7
第 3 天:8
第 4 天:9
第 5 天:10

请注意,货物必须按照给定的顺序装运,因此使用载重能力为 14 的船舶并将包装分成 
(2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 


示例 2:

输入:weights = [3,2,2,4,1,4], D = 3
输出:6
解释:
船舶最低载重 6 就能够在 3 天内送达所有包裹,如下所示:
第 1 天:3, 2
第 2 天:2, 4
第 3 天:1, 4
示例 3:

输入:weights = [1,2,3,1,1], D = 4
输出:3
解释:
第 1 天:1
第 2 天:2
第 3 天:3
第 4 天:1, 1
 

提示:

1 <= D <= weights.length <= 50000
1 <= weights[i] <= 500

算法1

二分逐步逼近 最小的装载量

C++ 代码

class Solution {
public:


bool check(vector<int>& weights, int board, int D) {
    int sum = 0;
    int l = 0; 
    int t = 1;
    while (l < weights.size()) {
        sum += weights[l];
        if (sum >= board) {
            sum = 0;
            t++;
            if (t > D) return false;
        }
        else {
            l++;
        }
    }

    if (t <= D) return true;

    return false;
}

int shipWithinDays(vector<int>& weights, int D) {
    int l = 1; int r = 50010*500;

    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (!check(weights,mid,D)) l = mid;
        else r = mid - 1;
    }

    cout << l;
    return l;

    return 0;
}


};




itdef
6天前

题目描述

H城是一个旅游胜地,每年都有成千上万的人前来观光。

为方便游客,巴士公司在各个旅游景点及宾馆,饭店等地都设置了巴士站并开通了一些单程巴士线路。

每条单程巴士线路从某个巴士站出发,依次途经若干个巴士站,最终到达终点巴士站。

一名旅客最近到H城旅游,他很想去S公园游玩,但如果从他所在的饭店没有一路巴士可以直接到达S公园,
则他可能要先乘某一路巴士坐几站,再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。

现在用整数1,2,…N 给H城的所有的巴士站编号,约定这名旅客所在饭店的巴士站编号为1,S公园巴士站的编号为N。

写一个程序,帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程中换乘的次数最少。

输入格式
第一行有两个数字M和N,表示开通了M条单程巴士线路,总共有N个车站。

从第二行到第M+1行依次给出了第1条到第M条巴士线路的信息,其中第i+1行给出的是第i条巴士线路的信息,
从左至右按运行顺序依次给出了该线路上的所有站号,相邻两个站号之间用一个空格隔开。

输出格式
共一行,如果无法乘巴士从饭店到达S公园,则输出”NO”,否则输出最少换乘次数,换乘次数为0表示不需换车即可到达。

数据范围
1≤M≤100,
1≤N≤500
输入样例:
3 7
6 7
4 7 3 6
2 1 3 5
输出样例:
2

算法1

BFS
建图 每个车站到达后面的车站的距离都是1
那么1到达n的最短距离就是转车次数+1

比如例题中
1到2 3 5 都是距离1
2到 1 3 5 都是距离1
1先到3 3再到7 就是1到7的最短距离

C++ 代码

// 123145.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <sstream>
#include <queue>

using namespace std;

const int N = 510;

int n, m;
int stop[N];
/*
3 7
6 7
4 7 3 6
2 1 3 5
输出样例:
2
*/
int g[N][N];


int bfs()
{
    queue<pair<int,int>> q;

    for (int i = 1; i <= n; i++) {
        if (g[1][i] != 0) {
            q.push({ i,0 });
            g[1][i] = 0;
        }
    }


    while (q.size()) {
        int currentStop = q.front().first;
        int step = q.front().second;
        q.pop();
        if (currentStop == n) return step;
        for (int i = 1; i <= n; i++) {
            if (g[currentStop][i] != 0) {
                q.push({ i ,step+1});
                g[currentStop][i] = 0;
            }
        }
    }


    return -1;
}

int main()
{
    cin >> m >> n;
    string line;
    getline(cin, line);
    while (m--) {
        getline(cin, line);
        stringstream ssin(line);
        int cnt = 0, p;
        while (ssin >> p) stop[cnt++] = p;

        //每个汽车的前站达到后站的距离都为1 因为是同一辆车 未换车
        for (int i = 0; i < cnt; i++) {
            for (int j = i + 1; j < cnt; j++) {
                g[stop[i]][stop[j]] = 1;
            }
        }
    }

    int ret = bfs();
    if(-1==ret) cout << "NO" <<endl;
    else cout << ret <<endl;

    return 0;
}



算法2

dijkstra

C++ 代码

// 123145.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <sstream>
#include <memory.h>
#include <queue>

using namespace std;

const int N = 510;

int n, m;
int stop[N];
/*
3 7
6 7
4 7 3 6
2 1 3 5
输出样例:
2
*/
int g[N][N];
int dist[N];
bool st[N];

int dij()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (t == -1 || dist[t] > dist[j])) {
                t = j;
            }
        }

        for (int j = 1; j <= n; j++) {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }

        st[t] = true;
    }

    return dist[n];
}


int main()
{
    cin >> m >> n;
    memset(g, 0x3f, sizeof g);
    string line;
    getline(cin, line);
    while (m--) {
        getline(cin, line);
        stringstream ssin(line);
        int cnt = 0, p;
        while (ssin >> p) stop[cnt++] = p;

        //每个汽车的前站达到后站的距离都为1 因为是同一辆车 未换车
        for (int i = 0; i < cnt; i++) {
            for (int j = i + 1; j < cnt; j++) {
                g[stop[i]][stop[j]] = 1;
            }
        }
    }

    int ret = dij();


    if ( ret > 0x3f3f3f3f/2) cout << "NO" << endl;
    else cout << ret-1 << endl;

    return 0;
}



算法3

spfa

C++ 代码

// 123145.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <sstream>
#include <queue>
#include <vector>
#include <memory.h>

using namespace std;

const int N = 510;

int n, m;
int stop[N];
/*
3 7
6 7
4 7 3 6
2 1 3 5
输出样例:
2
*/
vector<pair<int, int>> g[N];
int dist[N];
bool st[N];

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = 0; i < g[t].size(); i++) {
            int j = g[t][i].first;
            int w = g[t][i].second;
            if (dist[j] > dist[t] + w) {
                dist[j] = dist[t] + w;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];
}



int main()
{
    cin >> m >> n;

    string line;
    getline(cin, line);
    while (m--) {
        getline(cin, line);
        stringstream ssin(line);
        int cnt = 0, p;
        while (ssin >> p) stop[cnt++] = p;

        //每个汽车的前站达到后站的距离都为1 因为是同一辆车 未换车
        for (int i = 0; i < cnt; i++) {
            for (int j = i + 1; j < cnt; j++) {
                g[stop[i]].push_back({ stop[j],1 });
            }
        }
    }

    int ret = spfa();

    if (ret == 0x3f3f3f3f) cout << "NO" << endl;
    else cout << ret -1 << endl;


    return 0;
}



新鲜事 原文

itdef
6天前
突然发现自己saber排行370. 不是第370名,是第370页。 伤心的一天



itdef
6天前

题目描述

年轻的探险家来到了一个印第安部落里。

在那里他和酋长的女儿相爱了,于是便向酋长去求亲。

酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。

探险家拿不出这么多金币,便请求酋长降低要求。

酋长说:”嗯,如果你能够替我弄到大祭司的皮袄,我可以只要8000金币。
如果你能够弄来他的水晶球,那么只要5000金币就行了。”

探险家就跑到大祭司那里,向他要求皮袄或水晶球,大祭司要他用金币来换,
或者替他弄来其他的东西,他可以降低价格。

探险家于是又跑到其他地方,其他人也提出了类似的要求,或者直接用金币换,
或者找到其他东西就可以降低价格。

不过探险家没必要用多样东西去换一样东西,因为不会得到更低的价格。

探险家现在很需要你的帮忙,让他用最少的金币娶到自己的心上人。

另外他要告诉你的是,在这个部落里,等级观念十分森严。

地位差距超过一定限制的两个人之间不会进行任何形式的直接接触,包括交易。

他是一个外来人,所以可以不受这些限制。

但是如果他和某个地位较低的人进行了交易,地位较高的的人不会再和他交易,
他们认为这样等于是间接接触,反过来也一样。

因此你需要在考虑所有的情况以后给他提供一个最好的方案。

为了方便起见,我们把所有的物品从1开始进行编号,酋长的允诺也看作一个物品,
并且编号总是1。

每个物品都有对应的价格P,主人的地位等级L,
以及一系列的替代品Ti和该替代品所对应的”优惠”Vi。

如果两人地位等级差距超过了M,就不能”间接交易”。

你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。

输入格式
输入第一行是两个整数M,N,依次表示地位等级差距限制和物品的总数。

接下来按照编号从小到大依次给出了N个物品的描述。

每个物品的描述开头是三个非负整数P、L、X,
依次表示该物品的价格、主人的地位等级和替代品总数。

接下来X行每行包括两个整数T和V,分别表示替代品的编号和”优惠价格”。

输出格式
输出最少需要的金币数。

数据范围
1≤N≤100,
1≤P≤10000,
1≤L,M≤N,
0≤X<N
输入格式
1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0
输出格式
5250

算法1

根据题意来说 是建立一个有向图 边权值就是可交换物品时的支付金币。另新增一个虚拟起始点,到各个点的边权值就是货物的金币值。 答案就是虚拟起点到点1的最短路径。
最短路使用dijkstra spfa均可。
还要注意最短路径上的各个点的等级差值不能超过要求,所以需要使用上下限值的多次求最短路

C++ 代码

// 11234.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>


using namespace std;

int diff, id;

const int N = 200;
const int INF = 0x3f3f3f3f;

int level[N];
int dist[N];
bool st[N];
int g[N][N];

int dij( int down,int up)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[0] = 0;

    for (int i = 0; i <= id; i++) {
        int t = -1;
        for (int j = 0; j <= id; j++) {
            if (!st[j] && (t == -1 || dist[t] > dist[j])) {
                t = j;
            }
        }

        for (int j = 1; j <= id; j++) {
            if(level[j] >= down && level[j] <= up)
                dist[j] = min(dist[j], dist[t] + g[t][j]);
        }

        st[t] = true;
    }

    //if (dist[1] == 0x3f3f3f3f) return -1;
    return dist[1];

}


int main()
{
    cin >> diff >> id;
    memset(g, 0x3f, sizeof g);

    for (int i = 1; i <= id; i++) {
        int p, l, x;
        cin >> p >> l >> x;
        level[i] = l;
        g[0][i] = p;
        for (int j = 0; j < x; j++) {
            int a, b;
            cin >> a >> b;
            g[a][i] = b;
        }
    }

    //跑最短路 获得从0开始到1的最短距离
    int ret = INF;

    for (int i = level[1] - diff; i  <= level[1] ; i++) {
        ret =  min(ret, dij(i,i+diff));
    }

    cout << ret << endl;

    return 0;
}



算法2

spfa方法,注意 spfa中虚拟起点也要进入队列参与计算,所以为了避免被等级差的规则被排除在外,将 虚拟起点的等级调整为点1起点相同。

C++ 代码

// 11234.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <memory.h>


using namespace std;

int diff, id;

const int N = 200;
const int INF = 0x3f3f3f3f;

int level[N];
bool st[N];
int dist[N];

vector<pair<int, int>> g[N];

int spfa(int down,int up)
{
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0;

    queue<int> q;
    q.push(0);
    st[0] = true;

    while (q.size()) {
        int t = q.front(); q.pop();
        st[t] = false;

        if (level[t]<down || level[t] >up)
            continue;

        for (int i = 0; i < g[t].size(); i++) {
            int j = g[t][i].first;
            int w = g[t][i].second;
            if (dist[j] > dist[t] + w) {
                dist[j] = dist[t] + w;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }


    return dist[1];
}


int main()
{
    cin >> diff >> id;

    for (int i = 1; i <= id; i++) {
        int p, l, x;
        cin >> p >> l >> x;
        level[i] = l;
        //g[0][i] = p;
        g[0].push_back({ i,p });
        for (int j = 0; j < x; j++) {
            int a, b;
            cin >> a >> b;
            //g[a][i] = b;
            g[a].push_back({ i,b });
        }
    }

    int ret = INF;
    level[0] = level[1];
    for (int i = level[1] - diff; i <= level[1]; i++) {
        ret = min(ret, spfa(i, i + diff));
    }

    cout << ret;

    return 0;
}