#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];
}
map<pii,bool>vis;
int ans=0;
while(!q.empty())
{
int c=q.top()[0], x=q.top()[1], last=q.top()[2];
q.pop();
if (vis[{x,fin(last)}]) 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[{x,last}]=1;
for(auto y:a[x])
{
if (!vis[{y.fi,par[x]}] && 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 |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
7416 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3416 KB |
Output is correct |
| 3 |
Execution timed out |
6063 ms |
420680 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
