#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 fact(int x)
//{
// int w=1;
// forr(i,1,x+1) w*=i;
//////}
//bool cmp(pair<int,pii> a, pair<int,pii> b)
//{
// if (get<0>(a)==get<0>(b) && get<1>(a)==get<1>(b)) return get<2>(a)<get<2>(b);
// if (get<0>(a)==get<0>(b)) return get<1>(a)<get<1>(b);
// return get<0>(a)<get<0>(b);
//}
signed main()
{
// #ifndef LOCAL
// freopen("lifeguards.in","r",stdin);
// freopen("lifeguards.out","w", stdout);
// #endif
fast
int n,m,k;
cin>>n >>m >>k;
// vector<pii> a[n+1];
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;
}
}
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[n];
bool b[n+1]= { };
forr(i,0,k)
{
cin>>s[i];
b[s[i]]=1;
}
vector<pii> top3[n+1];
forr(i,1,n+1)
{
vector<pii> cur;
forr(j,1,n+1)
{
if (i==j) continue;
forr(k,1,n+1)
{
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
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) cur+=top3[y][0].fi;
else if (top3[y].sz==1) continue;
else if (top3[y][1].se!=nope) cur+=top3[y][1].fi;
else if (top3[y].sz==2) continue;
else cur+=top3[y][2].fi;
//cout<<x<<' '<<y<<' '<<cur<<endl;
ans=min(ans,cur);
}
}
if (ans==bigg) ans/=0;
cout<<ans;
return 0;
}
Compilation message
RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:113:23: warning: division by zero [-Wdiv-by-zero]
113 | if (ans==bigg) ans/=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 |
Runtime error |
629 ms |
1048576 KB |
Execution killed with signal 9 |
| 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 |
- |
