This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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>
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;
}
}
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 && 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;
}
Compilation message (stderr)
RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:102:23: warning: division by zero [-Wdiv-by-zero]
102 | if (ans==bigg) ans/=0;
| ~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |