[HOJ]83 FOMI洗腦計畫

Dijkstra

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define INF 1000000000
using namespace std;
struct node{
    int pos,val;
};
struct pt{
    int pa,now,val;
    friend bool operator <(pt a,pt b){
        return a.val>b.val;
    }
};

priority_queue<pt> pq;
vector<node> v[3005];
int n,k,p,m,fr,to,val,dis[3005],pa[3005],ans;

int main(){
    scanf("%d%d%d",&n,&k,&m);
    for(int i=0;i<=n;i++)dis[i]=INF;
    for(int i=0;i<k;i++){
        scanf("%d%d%d",&fr,&to,&val);
        v[fr].push_back(node{to,val});
        v[to].push_back(node{fr,val});
    }
    while(m--){
        scanf("%d",&fr);
        dis[fr]=0;
        pa[fr]=fr;
        pq.push(pt{fr,fr,0});
    }
    while(!pq.empty()){
        p=pq.top().pa;
        fr=pq.top().now;
        pq.pop();
        for(int i=0;i<v[fr].size();i++){
            if(dis[fr]+v[fr][i].val<dis[v[fr][i].pos]){
                dis[v[fr][i].pos]=dis[fr]+v[fr][i].val;
                pa[v[fr][i].pos]=p;
                pq.push(pt{p,v[fr][i].pos,dis[v[fr][i].pos]});
            }
        }
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,dis[i]);
        for(int j=0;j<v[i].size();j++){
                k=dis[i]+dis[v[i][j].pos]+v[i][j].val+1;
                ans=max(ans,k/2);
        }
    }
    printf("%d\n",ans);
}