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