dijk写法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 2010, M = 200010;
int n, m, k, t;
int e[M], ne[M], h[N], w[M], idx, a[N];
int d[N];
bool st[N];
priority_queue<PII, vector<PII>, greater<PII>> heap;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void spfa()
{
while(heap.size())
{
auto t = heap.top();
heap.pop();
int x = t.second;
if(st[x]) continue;
st[x] = true;
for(int i = h[x]; i != -1; i = ne[i])
{
int y = e[i], z = w[i];
if(d[z] > max(d[x], d[y]) + max(a[x], a[y]))
{
d[z] = max(d[x], d[y]) + max(a[x], a[y]);
heap.push({d[z], z});
}
}
}
}
int main()
{
cin >> n >> m >> k >> t;
memset(h, -1, sizeof h);
for(int i = 1; i <= n; i ++ ) cin >> a[i];
memset(d, 0x3f, sizeof d);
while(m -- )
{
int x;
cin >> x;
d[x] = 0;
heap.push({0, x});
}
while(k -- )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
spfa();
cout << d[t] << endl;
return 0;
}
spfa写法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2010, M = 200010;
int n, m, k, t;
int e[M], ne[M], h[N], w[M], idx, a[N];
int d[N];
bool st[N];
queue<int> q;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void spfa()
{
while(q.size())
{
int x = q.front();
q.pop();
st[x] = false;
for(int i = h[x]; i != -1; i = ne[i])
{
int y = e[i], z = w[i];
if(d[z] > max(d[x], d[y]) + max(a[x], a[y]))
{
d[z] > max(d[x], d[y]) + max(a[x], a[y]);
if(!st[z])
{
st[z] = true;
q.push(z);
}
}
}
}
}
int main()
{
cin >> n >> m >> k >> t;
memset(h, -1, sizeof h);
for(int i = 1; i <= n; i ++ ) cin >> a[i];
memset(d, 0x3f, sizeof d);
while(m -- )
{
int x;
cin >> x;
d[x] = 0;
q.push(x);
st[x] = true;
}
while(k -- )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
spfa();
cout << d[t] << endl;
return 0;
}