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;
}