2023牛客寒假算法基础集训营6-I-阿宁前往沙城

Solost

2023 年 02 月 11 日

190 次浏览

暂无评论

2217字数

题目题解

![image.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F02%2F11%2Fimage.png)

[题目链接](https://ac.nowcoder.com/acm/contest/46814/I)

---

## solution

这道题目用的是dijkstra，如果边数大于最短路径，那么就可以认为我们的最短路径就是dist[n]，因为我们可以挑选一条不用的路摧毁，然后每经过以后摧毁走过的路就好，所以dist[n]就是最短1-n经过最少数目的点，因为权值是1，如果小于等于的话，那么我们在第一次走的时候就不能摧毁任何一条路，我们可以走过第一条路到达2，然后每次摧毁走过的路，那么值就是dist[n] - 1 + c,c是1-2那条路的权值，减去1是把第一条路的1权值删去，加上本来的权值，因为第一次第一条路是不能先摧毁的。

---

用vector模拟邻接表的操作

```cpp
vector<vector<PII>> h[N] //这个操作就是开了大小为N的vector的vector，可以做到第一维度是头，
例如，1-2，1-3，2-3，那么h[2] = {2， 3}，h[2] = {3}
```

---

```
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;

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

vector<PII> h[N];

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({ 0, 1 }); // 前一个是距离，后一个是

while (heap.size()) {
        auto t = heap.top();
        heap.pop();

int ver = t.y, distance = t.x;

if (st[ver])
            continue;
        st[ver] = true;

for (int i = 0; i < (int)h[ver].size(); i++) {
            int j = h[ver][i].x;
            int d = h[ver][i].y;
            d = 1;
            // if(h[ver].size() > 2) d = 1;
            if (dist[j] > dist[ver] + d) {
                dist[j] = dist[ver] + d;
                heap.push({ dist[j], j });
            }
        }
    }

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

int main()
{
    scanf("%d%d", &n, &m);
    int t = m;
    while (t--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (a != b) {
            h[a].push_back({ b, c });
            h[b].push_back({ a, c });
        }
    }
    dijkstra();
    if (m > dist[n])
        cout << dist[n];
    else
        cout << h[1][0].y + dist[n] - 1;
    return 0;
}
```

最后修改：2023 年 02 月 11 日