ADRABR - Adrita and Her Bike Ride 题解

1.题目大意

题目传送门

2.思路

因为每条道路长均为 \(1km\)，所以我们可以在建边时就加上走这条路的初始成本，即对于每条边的两端 \(a,b\) 和通行费 \(w\)，我们直接 \(add (a,b,w+12)\)即可。

再就是由于是多组数据，所以我们在每次输入前要清空数组，然后跑一遍最短路模板即可。

3.代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define int long long

using namespace std;

const int N = 1000010;
typedef pair <int, int> PII;

int n, m, ss, tt;
int h[N], w[N], e[N], ne[N];
int dis[N], st[N];
int idx;

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

int dijkstra (int s, int t) {
	memset (dis, 127, sizeof dis);
	dis[s] = 0;

	priority_queue <PII, vector <PII>, greater <PII> > p;
	p.push ({0, s});

	while (!p.empty ()) {
		auto t = p.top ();
		p.pop ();

		int ver = t.second, dit = t.first;

		if (st[ver]) {
			continue;
		}

		st[ver] = true;
		for (int i = h[ver]; i != -1; i = ne[i]) {
			int j = e[i];
			if (dis[j] > dit + w[i]) {
				dis[j] = dit + w[i];
				p.push ({dis[j], j});
			}
		}
	}

	return dis[t];
}

signed main () {
	int T;
	cin >> T;

	while (T --) {
		cin >> n >> m >> ss >> tt;
		memset (h, -1, sizeof h);
		memset (st, false, sizeof st);
		
		while (m --) {
			int a, b, c;
			cin >> a >> b >> c;
			add (a, b, c + 12);
			add (b, a, c + 12);
		}

		cout << dijkstra (ss, tt) << endl;
	}
	return 0;
}