#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>using ordered_set = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;//find_by_order(ind);
//order_of_key()
#define int long long
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define yes "YES"
#define no "NO"
#define bigg INT_MAX
#define debug(x) cout<<(#x)<<" = " <<x<<endl;
#define all(x) x.begin(),x.end()
#define sz size()
#define nn '\n'
#define mms(x,y) memset(x,y,sizeof(x))
#define forr(i,j,n) for (int i=j; i<n; i++)
#define forn(i,j,n) for (int i=j; i>n; i--)
#define fi first
#define se second
#define la "LA"
#define cinn(x,y) for(int i=0; i<y; i++) cin>>x[i];
#define pii pair<int,int>
int par[100005]={ };
int fin(int x)
{
if (x==par[x]) return x;
return par[x]=fin(x);
}
signed main()
{
// #ifndef LOCAL
// freopen("lifeguards.in","r",stdin);
// freopen("lifeguards.out","w", stdout);
// #endif
fast
int n,m,k;
cin>>n >>m >>k;
// int dis[n+1][n+1];
// forr(i,1,n+1)
// {
// forr(j,1,n+1)
// {
// if (i==j) dis[i][j]=0;
// else dis[i][j]=bigg;
// }
// }
vector<pii> a[n+1];
forr(i,0,m)
{
int x,y,z;
cin>>x >>y >>z;
a[x].pb({y,z});
a[y].pb({x,z});
// dis[x][y]=z;
// dis[y][x]=z;
}
int s[k];
priority_queue<array<int,3>> q;
bool b[n+1]= { };
// int last[n+1]={ };
forr(i,0,k)
{
cin>>s[i];
if (s[i]==1 || s[i]==2) continue;
q.push({0,s[i],s[i]});
b[s[i]]=1;
par[s[i]]=s[i];
// last[s[i]]=s[i];
}
set <pii>vis;
int ans=0;
while(!q.empty())
{
int c=q.top()[0], x=q.top()[1], last=q.top()[2];
q.pop();
if (vis.find({x,fin(last)})!=vis.end()) continue;
par[x]=fin(last);
// cout<<c<<' '<<x<<endl;
if (b[x] && c!=0)
{
// cout<<x<<' '<<c<<endl;
ans=-c;
break;
}
// if (!b[x])
vis.insert({x,par[x]});
// cout<<"PUT"<<x<<' '<<last<<endl;
for(auto y:a[x])
{
// cout"DWAR"<<y.fi<<' '<<par[x]<<endl;
if (vis.find({y.fi,par[x]})==vis.end() && par[x]!=y.fi)
{
int o=abs(c);
o+=y.se;
q.push({-o,y.fi,par[x]});
// cout<<yes<<y.fi<<' '<<y.se<<' '<<last<<endl;
}
}
}
cout<<ans+1;
// vector<pii> top3[n+1];
// forr(q,1,n+1)
// {
// //vector<pii> cur;
// forr(i,1,n+1)
// {
//
// forr(j,1,n+1)
// {
// if (i==j) continue;
// dis[i][j]=min(dis[i][j],dis[i][q]+dis[q][j]);
// }
// //cout<<la<<i<<' '<<j<<' '<<dis[i][j]<<endl;
// }
////if (b[i] && b[j]) cur.pb({dis[i][j],j});
//// sort(all(cur));
//// if(cur.sz>0) top3[i].pb(cur[0]);
//// if(cur.sz>1) top3[i].pb(cur[1]);
//// if(cur.sz>2) top3[i].pb(cur[2]);
// }
// forr(i,1,n+1)
// {
// vector<pii> cur;
// forr(j,1,n+1)
// {
// if (i==j) continue;
// if (b[i] && b[j]) cur.pb({dis[i][j],j});//cout<<la<<i<<' '<<j<<' '<<dis[i][j]<<endl;
// }
// sort(all(cur));
// if(cur.sz>0) top3[i].pb(cur[0]);
// if(cur.sz>1) top3[i].pb(cur[1]);
// if(cur.sz>2) top3[i].pb(cur[2]);
// }
// int ans=bigg;
// forr(i,0,k)
// {
// int x=s[i];
// if (top3[x].sz==0) continue;
// forr(j,0,k)
// {
// if (i==j) continue;
// int y=s[j];
// int cur=top3[x][0].fi;
// int nope=top3[x][0].se;
// if (y==nope) continue;
// if (top3[y].sz==0) continue;
// if (top3[y][0].se!=nope && top3[y][0].se!=x) cur+=top3[y][0].fi;
// else if (top3[y].sz==1) continue;
// else if (top3[y][1].se!=nope && top3[y][1].se!=x) cur+=top3[y][1].fi;
// else if (top3[y].sz==2) continue;
// else if (top3[y][2].se!=nope && top3[y][2].se!=x) cur+=top3[y][2].fi;
// else if (top3[y].sz==3) continue;
// else cur+=top3[y][3].fi;
// // cout<<x<<' '<<y<<' '<<cur<<endl;
// ans=min(ans,cur);
// }
// }
// if (ans==bigg) ans/=0;
// cout<<ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
8076 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3420 KB |
Output is correct |
| 3 |
Correct |
1672 ms |
218008 KB |
Output is correct |
| 4 |
Correct |
604 ms |
94128 KB |
Output is correct |
| 5 |
Correct |
169 ms |
21220 KB |
Output is correct |
| 6 |
Correct |
47 ms |
13024 KB |
Output is correct |
| 7 |
Correct |
187 ms |
26304 KB |
Output is correct |
| 8 |
Correct |
27 ms |
9048 KB |
Output is correct |
| 9 |
Correct |
42 ms |
12100 KB |
Output is correct |
| 10 |
Correct |
31 ms |
9720 KB |
Output is correct |
| 11 |
Correct |
1525 ms |
260536 KB |
Output is correct |
| 12 |
Correct |
36 ms |
10840 KB |
Output is correct |
| 13 |
Correct |
451 ms |
68784 KB |
Output is correct |
| 14 |
Correct |
77 ms |
18384 KB |
Output is correct |
| 15 |
Correct |
1569 ms |
258212 KB |
Output is correct |
| 16 |
Correct |
41 ms |
9300 KB |
Output is correct |
| 17 |
Correct |
674 ms |
136604 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3676 KB |
Output is correct |
| 19 |
Correct |
1174 ms |
190984 KB |
Output is correct |
| 20 |
Correct |
89 ms |
17356 KB |
Output is correct |
| 21 |
Correct |
55 ms |
14576 KB |
Output is correct |
| 22 |
Correct |
29 ms |
9556 KB |
Output is correct |
| 23 |
Correct |
15 ms |
6236 KB |
Output is correct |
| 24 |
Correct |
1406 ms |
226784 KB |
Output is correct |
| 25 |
Correct |
54 ms |
11456 KB |
Output is correct |
| 26 |
Correct |
27 ms |
8960 KB |
Output is correct |
| 27 |
Correct |
33 ms |
10320 KB |
Output is correct |
| 28 |
Correct |
13 ms |
4956 KB |
Output is correct |
| 29 |
Correct |
65 ms |
16244 KB |
Output is correct |
| 30 |
Correct |
208 ms |
33652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
