• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 做题记录 Luogu P5304

4小时前 2次浏览

P5304 [GXOI/GZOI2019]旅行者 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

``````#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x1f1f1f1f1f1f1f1f
#define N 4000005
int n, m, k;
struct node
{
int val, num, from;
};
bool operator < (node a, node b)
{
return a.val > b.val;
}
priority_queue<node> q;
node dis[N], dis1[N];
int first[N], Next[N], to[N], w[N], tot;
int uu[N], vv[N], ww[N];
int vis[N], a[N];
void add(int x, int y, int z)
{
Next[++tot] = first[x];
first[x] = tot;
to[tot] = y;
w[tot] = z;
return;
}
void dijkstrar()
{
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++)
{
dis[i].val = inf;
dis[i].num = -1;
dis[i].from = -1;
}
for(int i = 1; i <= k; i++)
{
dis[a[i]].val = 0;
dis[a[i]].num = a[i];
dis[a[i]].from = a[i];
q.push(dis[a[i]]);
}
while(!q.empty())
{
node u = q.top();
q.pop();
if(vis[u.num])
{
continue;
}
vis[u.num] = 1;
for(int i = first[u.num]; i; i = Next[i])
{
int v = to[i];
if(u.val + w[i] < dis[v].val)
{
dis[v].val = u.val + w[i];
dis[v].num = v;
dis[v].from = u.from;
q.push(dis[v]);
}
}
}
return;
}
signed main()
{
//freopen("tour.in", "r", stdin);
//freopen("tour.out", "w", stdout);
int T;
scanf("%lld", &T);
while(T--)
{
tot = 0;
memset(first, 0, sizeof(first));
scanf("%lld%lld%lld", &n, &m, &k);
for(int i = 1; i <= m; i++)
{
scanf("%lld%lld%lld", &uu[i], &vv[i], &ww[i]);
}
for(int i = 1; i <= k; i++)
{
scanf("%lld", &a[i]);
}
dijkstrar();
for(int i = 1; i <= n; i++)
{
dis1[i] = dis[i];
}
tot = 0;
memset(first, 0, sizeof(first));
for(int i = 1; i <= m; i++)
{
}
dijkstrar();
int ans = inf;
for(int i = 1; i <= m; i++)
{
if(dis1[uu[i]].from != dis[vv[i]].from)
{
ans = min(ans, dis1[uu[i]].val + dis[vv[i]].val + w[i]);
}
}
printf("%lldn", ans);
}
return 0;
}
``````