Create a gist now

Instantly share code, notes, and snippets.

@oldsnuke /2011ho3www Secret
Created Feb 15, 2011

What would you like to do?
meiso
#include<cstdio>
#include<algorithm>
#include<stack>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<cmath>
#include<map>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define drep(i,n) for(int i = n; i >= 0; i--)
using namespace std;
const int INF = 100000001;
struct g{int f,t,h;};
struct w{int x,u;};
struct o{int y,p,r;};
vector<g> e;
vector<w> v[3001];
int s[3001];
queue<o> q;
int c[3001];
int main(){
int n, m, k, a, b, l, ans = 0;
o z;
scanf("%d%d%d", &n, &m, &k);
rrep(i,n) s[i] = INF;
rep(i,m){
scanf("%d%d%d",&a,&b,&l);
e.push_back((g){a,b,l});
v[a].push_back((w){b,l});
v[b].push_back((w){a,l});
}
rep(i,k){scanf("%d",&a);q.push((o){0,a,0});}
while(!q.empty()){
z = q.front(); q.pop();
if(s[z.p] >= z.r){
c[z.p] = z.y;
s[z.p] = z.r;
rep(i,v[z.p].size()){
q.push((o){z.p,v[z.p][i].x,z.r+v[z.p][i].u});
}
}
}
rrep(i,n){
ans = max(ans,s[i]);
}
rep(i,e.size()){
if(c[e[i].f] != e[i].t && c[e[i].t] != e[i].f){
ans = max(ans,(s[e[i].f] + s[e[i].t] + e[i].h+1)/2);
}
}
printf("%d\n",ans);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment